<h2>题意</h2>

求有多少个子集族，满足:

1. 其中任意一个子集都是 $[n]$ 的子集;
2. 任意两个子集互不相同;
3. $1,2,\cdots ,n$ 都在其中至少出现了 $2$ 次。

答案对 $M$ 取模。
$2 \leq N \leq 3000,10^8 \leq M\leq 10^9 +9$，$M$ 是质数。

<h2>题解</h2>

dyls 说：看到子集族先想到容斥我太菜了
考虑容斥：现在我们是需要数限定一些数只能出现 $0$ 或 $1$ 次，其他数随意出现的方案数。数之间是没有顺序的，所以可以只枚举这样的数的个数，然后计算。令 $g_i$ 表示有 $i$ 个数只能在子集族的元素中出现 $0$ 或 $1$ 次，其他数无限制的方案数，那么答案就是：
$$2^{2^n} - \sum_{i=1}^n (-1)^i \binom n i g_i$$
现在我们考虑如何去算出 $g_i$，一开始的想法可能是去枚举有多少个出现了 $0$ 次，多少个出现了 $1$ 次，然后我们发现我们并不知道有哪些子集可以包含它，但是注意到这题只需要 $O(n^2)$ 的做法，所以我们可以考虑去枚举有多少个子集包含这些数。设有 $j$ 个子集包含了，那么现在的子集族由两部分组成：一部分是子集内全是无限制的数的集合，另一部分是子集内有限制的集合。前一种的贡献显然是 $2^{2^{n-i}}$，后一种的贡献大概就是考虑被限制的数应该被分到这些集合中，但是要注意有些数可以不出现，所以我们可以新建一个集合来表示不出现的数，也就是 $\left &#92;{^{i+1}_ {j+1} \right &#92;}$，然后发现无限制的数也可以加入到这些集合中，所以还有贡献 $(2^{n-i})^j$。
所以 $g_i$ 的计算过程就十分明了了！：
$$g_i = \sum_{j=0}^i 2^{2^{n-i}}\left &#92;{^{i+1}_ {j+1} \right &#92;}(2^{n-i})^j$$
预处理一下卡卡常就过去了。

<h2>代码</h2>

/*
 * sto Qingyu orz
 * 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴,
 * 使其天天爆零
 * 我不由自主地膜拜真神sqy。
 * Author: RainAir
 * Time: 2019-10-17 14:31:56
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3000+5;
int ha;
int n;
int SMAXN,fac[MAXN],inv[MAXN],facfac[MAXN];

inline int qpow(int a,int n=ha-2,int mod=ha){
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%mod;
        a = 1llaa%mod;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1llfac[i-1]i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1llinv[i+1](i+1)%ha;
    S0 = 1;
    FOR(i,1,MAXN-1){
//        Si = 1;
        FOR(j,1,i){
            Si = (Si-1+1lljSi-1%ha)%ha;
        }
    }
    FOR(i,0,MAXN-1) facfac[i] = qpow(2,qpow(2,i,ha-1));
}

inline int C(int n,int m){
    return 1llfac[n]inv[m]%ha*inv[n-m]%ha;
}

int main(){
    scanf("%d%d",&n,&ha);
    prework();int ans = facfac[n];
    FOR(i,1,n){
        int gx = 0,t1 = 1,b1 = qpow(2,n-i);
        FOR(j,0,i){
            //(gx += 1llqpow(2,qpow(2,n-i,ha-1))qpow(qpow(2,n-i),j)%ha*Si+1%ha) %= ha;
            (gx += 1llfacfac[n-i]t1%ha*Si+1%ha) %= ha;
            t1 = 1llt1b1%ha;
        }
        gx = 1llgxC(n,i)%ha;
        if(i&1) gx = ha-gx;
        (ans += gx) %= ha;
    }
    printf("%dn",ans);
    return 0;
}