昨天写了忘发了。。

考虑容斥，设 $f(i)$ 表示钦定了 $i$ 个数只出现了 $\le 1$ 次时的方案数量，那么答案显然等于

$$ans = \sum_{i=0}^n (-1)^i f(i)$$

考虑我们钦定的 $i$ 个数，显然可以直接假定为 $1\sim i$ ，最后再乘个 $\binom n i$ 的系数即可。

先考虑除开前 $i$ 个的数，这些数是没有限制的，他们可以组成集合的方案数量是 $2^{2^{n-i}}$ 种，因为任何一个这 $n-i$ 个数的子集都可以作为某一种集合出现或者不出现。

再考虑前 $i$ 个数的加入。假设前 $i$ 个数出现在 $j$ 个集合里（因为每个数出现次数不超过 $1$ 所以前 $i$ 个数出现的集合个数 $j$ 也不会超过 $i$ ），考虑枚举这个 $j$ 。

现在我们已经确定了前 $i$ 个数会被分配到 $j$ 个集合里面，其中有些数可能直接被丢掉。然后有两种方法数这个：

• 考虑新建一个垃圾桶，用来放我们不放进这 $j$ 个集合里面的数。首先假定我们确定这 $i$ 个数在分配后有数在垃圾桶里，但是当我们把这 $i$ 个数分配进这 $j+1$ 个集合后，我们并不确定哪一个是垃圾桶，于是还得乘个 $(j+1)$ 的系数表示枚举哪一个是垃圾桶。还有的情况就是不存在分配在垃圾桶的数。我们知道 $i$ 个数分配进集合的方案数就是第二类斯特林数，于是这里就是

  $$(j+1)\begin{Bmatrix}i\\j + 1\end{Bmatrix} + \begin{Bmatrix}i\\j\end{Bmatrix} = \begin{Bmatrix}i + 1\\j + 1\end{Bmatrix}$$

  也就是第二类斯特林数的递推公式。

• 其实也可以考虑如果我们考虑新加一个 $0$ 进去，然后钦定 $0$ 被分配到的集合就是垃圾桶也是完全没有问题的。这样就可以直接得到答案是 $\begin{Bmatrix}i + 1\\j + 1\end{Bmatrix}$

最后记得在这 $j$ 个集合中也可以任意塞后 $n-i$ 个数中的数，而且明显这 $j$ 个集合不可能重，所以可以直接乘上系数 $(2^{n-i})^j$

代码

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 3006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
//#define P 998244353
int n , P;
int S[MAXN][MAXN] , C[MAXN][MAXN];

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int p2[MAXN];
void solve() {
	cin >> n >> P;
	S[0][0] = C[0][0] = 1 , p2[0] = 1;
	rep( i , 1 , n + 1 ) {
		C[i][0] = 1 , S[i][0] = 0;
		rep( j , 1 , i ) S[i][j] = ( S[i - 1][j - 1] + S[i - 1][j] * 1ll * j ) % P , C[i][j] = ( C[i - 1][j - 1] + C[i - 1][j] ) % P;
		p2[i] = p2[i - 1] * 2 % ( P - 1 );
	}
	int ans = 0;
	rep( i , 0 , n ) {
		int re = 0;
		rep( j , 0 , i ) re = ( re + S[i + 1][j + 1] * 1ll * Pow( 2 , ( n - i ) * 1ll * j % ( P - 1 ) ) ) % P;
		re = re * 1ll * Pow( 2 , p2[n - i] ) % P * C[n][i] % P;
		ans = ( ans + ( ( i & 1 ) ? P - re : re ) ) % P;
	}
	cout << ans << endl;
}

signed main() {
//	freopen("ex_A2.in","r",stdin);
//	freopen("out","w",stdout);
//	int T;cin >> T;while( T-- ) solve();
    solve();
}