problem
求有多少个子集族，满足：
1、其中任意一个子集都是([n])的子集（包括(phi)）；
2、任意两个子集互不相同；
3、(1,2,...,n)都在其中至少出现了(2)次。
答案对(M)取模。
(2leqslant Nleqslant 3000)，(10^8leqslant Mleqslant 10^9+9)，(M)是质数。
sol
（开个随笔记录思路以及细节的）
由于至少出现2次，而且(N)的范围很乐观，我们采用容斥（一般用于不好直接求解答案的大部分用容斥的思想）
我们以“出现次数小于2次”来进行容斥，先可以大体写出来这个式子
[ans=sum_{i=1}^N(-1)^i{Nchoose i}f(i)
]
现在看(f(i))。选出来了(i)个数要满足条件，剩余的(N-i)个数随便，这(N-i)个数构成的集合有(2^{N-i})种，那么可以有(2^{2^{N-i}})种选择方案。回头再来考虑这(i)个数怎么选。显然这(i)个数要么出现在某一集合中且只出现一次，要么没有出现。这里假定(i)个数被分到了(j+1)个集合中（+1是单独给没出现的数划的集合），再放入一个标记数字0表示这个数字所在集合为没出现数的集合。那么就是第二类斯特林数({i+1race j+1})，然后包含这些数的集合中又可以随便塞入其他(N-i)数中的任意组合，故每一个集合会带来(2^{N-i})的贡献，总共就是(2^{j(N-i)})。故
[f(i)=2^{2^{N-i}}sum_{j=0}^i2^{j(N-i)}{i+1race j+1}
]
综上
[ans=sum_{i=1}^N(-1)^i{Nchoose i}2^{2^{N-i}}sum_{j=0}^i2^{j(N-i)}{i+1race j+1}
]