#include <cstdio>
const int M = 3005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,g[M][M],C[M][M];
void add(int &x,int y) {x=(x+y)%m;}
int qkpow(int a,int b,int p)
{
	int r=1;
	while(b>0)
	{
		if(b&1) r=r*a%p;
		a=a*a%p;
		b>>=1;
	}
	return r;
}
signed main()
{
	n=read();m=read();g[0][0]=1;
	for(int i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			add(C[i][j],C[i-1][j-1]+C[i-1][j]);
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++)
		{
			if(j) add(g[i][j],g[i-1][j-1]);
			add(g[i][j],(j+1)*g[i-1][j]);
		}
	for(int i=0;i<=n;i++)
	{
		int z=C[n][i]*qkpow(2,qkpow(2,n-i,m-1),m)%m;
		int f=0,x=qkpow(2,n-i,m);if(i&1) z=m-z;
		for(int j=0,y=1;j<=i;j++,y=y*x%m)
			add(f,g[i][j]*y);
		add(ans,f*z);
	}
	printf("%lld\n",(ans+m)%m);
}