import std.stdio, std.algorithm, std.range, std.conv, std.string, std.math;
import core.stdc.stdio, core.bitop;
// foreach, foreach_reverse, writeln

void main() {
	int n, MOD;
	scanf("%d%d", &n, &MOD);
	
	long[][] c = new long[][](n+1,n+2);
	c[0][0] = 1;
	foreach (i; 0..n) {
		foreach (j; 0..i+1) {
			(c[i+1][j] += c[i][j]) %= MOD;
			(c[i+1][j+1] += c[i][j]) %= MOD;
		}
	}

	long[][] dp = new long[][](n+1,n+1);
	dp[0][0] = 1;
	foreach (i; 0..n) {
		foreach (j; 0..n+1) {
			(dp[i+1][j] += dp[i][j]) %= MOD;
			(dp[i+1][j] += dp[i][j]*j) %= MOD;
			if (j != n) (dp[i+1][j+1] += dp[i][j]) %= MOD;
		}
	}

	//long pow(long x, long times, long MOD) {
	//	long ret = 1;
	//	while (times) {
	//		if (times&1) (ret *= x) %= MOD;
	//		times >>= 1;
	//		(x *= x) %= MOD;
	//	}
	//	return ret;
	//}
	//long powpow(long x, long y, long MOD) {
	//	foreach (i; 0..y) {
	//		(x *= x) %= MOD;
	//	}
	//	return x;
	//}

	long[] p2 = new long[n+1];
	p2[0] = 1;
	foreach (i; 0..n) p2[i+1] = p2[i]*2%MOD;

	long[] pp2 = new long[n+1];
	pp2[0] = 2;
	foreach (i; 0..n) pp2[i+1] = pp2[i]*pp2[i]%MOD;

	long ans = 0;
	foreach (i; 0..n+1) {
		long cur = 0;
		long two = 1;
		foreach (j; 0..i+1) {
			long a = dp[i][j]*c[n][i]%MOD;
			//long x = powpow(2,n-i,MOD)*pow(pow(2,n-i,MOD),j,MOD)%MOD;
			long x = pp2[n-i]*two%MOD;
			(cur += a*x) %= MOD;
			(two *= p2[n-i]) %= MOD;
		}
		if (i%2 == 0) {
			ans += cur;
		} else {
			ans += MOD-cur;
		}
		ans %= MOD;
	}
	writeln(ans);
}