The problem can be rephrased as follows.

• There is a sequence of sets \(B=(\lbrace \rbrace,\lbrace \rbrace,\ldots,\lbrace \rbrace)\) of length \(N\).
• We can repeat the operation: “choose a set \(S\subset \lbrace 1,2,\ldots,N\rbrace\), and set \(B_i=S\) for each \(i\in S\).”
• How many possible final sequences \(B\) are there?

Below, we consider only those where \(B_i\neq \varnothing\) for all \(i\).

First, let us consider the decision problem: given a sequence of sets \(B\), can it be produced by the operations? This can be solved by looking at the operations in reverse order.

• Maintain a set \(I\) of already-removed indices. Initially, \(I=\varnothing\).
• Repeat the following operation X.
  • Find a set \(S\) satisfying:
    • For each \(i\in S\), either \(B_i=S\) or \(i\in I\).
    • There exists \(i\in S\) such that \(i\notin I\).
  • Replace \(I\) with \(I\cup S\).
• If we can eventually achieve \(I=\lbrace 1,2,\ldots,N\rbrace\), then \(B\) can be produced.

As it is, the sequence of reverse operations may not be unique, making counting difficult. We make the sequence of reverse operations unique as follows.

• Maintain a set \(I\) of already-removed indices. Initially, \(I=\varnothing\).
• Repeat the following operation Y.
  • Enumerate all sets \(S\) satisfying:
    • For each \(i\in S\), either \(B_i=S\) or \(i\in I\).
    • There exists \(i\in S\) such that \(i\notin I\).
  • Let the enumerated sets be \(S_1,S_2,\ldots\), and replace \(I\) with \(I\cup S_1\cup S_2\cup \ldots\).
• If we can eventually achieve \(I=\lbrace 1,2,\ldots,N\rbrace\), then \(B\) can be produced.

Now, it suffices to count the number of uniquely determined reverse operation sequences.

Let \(I_j\) be the value of \(I\) after the \(j\)-th operation Y, and \(C_j=I_j\setminus I_{j-1}\). We consider the number of possible \(\lbrace S_1,S_2,\ldots\rbrace\) when \(I_{j-1}\) and \(C_j\) are fixed.

For the first operation, \(S_1,S_2,\ldots\) form a partition of \(I_1\).

For \(j\geq 2\), let \(D_k=\lbrace i\in C_j\mid B_i=S_k\rbrace\) for each \(S_k\). By definition, \(D_1,D_2,\ldots\) form a partition of \(C_j\). When \(D_k\) is fixed, \(S_k\) must satisfy:

• \(S_k\setminus D_k\) is a subset of \(I_{j-1}\).
• \((S_k\setminus D_k)\cap C_{j-1}\) is non-empty.

Thus, the number of choices for \(S_k\) is \(2^{|I_{j-1}|}-2^{|I_{j-1}|-|C_{j-1}|}\).

We now turn this into a DP.

Here, we fix the set of indices that will eventually be non-empty and count them. Define \(\mathrm{dp'}[x][y]\) as “the number of ways, for a fixed set of \(x\) indices, to apply operation Y some number of times and reach a state where \(|I|=x\) and the size of the most recently added set is \(y\).”

When all \(a\) indices are removed in a single first operation, \(S_1,S_2,\ldots\) form a partition of the \(a\) indices, so \(\displaystyle \mathrm{dp'}[a][a]=\sum_{b=1}^a \left\{ {a \atop b} \right\}\) (where \(\left\{ {a \atop b} \right\}\) denotes the Stirling number of the second kind).

For the transition, suppose currently \(|I|=x\), \(|C|=y\), and the size of the next set to be added is \(a\). When fixing the \(x+a\) indices eventually used, the number of ways to choose the \(a\) indices that form the next \(C\) is \(\binom{x+a}{a}\).

When \(C\) is partitioned into \(b\) sets \(D_1,D_2,\ldots,D_b\), the coefficient is the product of:

• Number of ways to choose the next \(C\): \(\binom{x+a}{a}\)
• Number of ways to partition \(C\) into \(b\) parts: \(\left\{ {a \atop b} \right\}\)
• Number of ways to choose \(S_k\) for each \(D_k\): \((2^x-2^{x-y})^b\)

That is, \(\displaystyle \mathrm{dp'}[x+a][a]\leftarrow \binom{x+a}{a}\sum_{b=1}^a \left\{ {a \atop b} \right\}(2^x-2^{x-y})^b\mathrm{dp'}[x][y]\).

Computing this directly gives a quadruple loop over \(x,y,a,b\). To speed this up, we precompute \(\displaystyle \mathrm{coef}[x][b]=\sum_{y=1}^x\mathrm{dp'}[x][y](2^x-2^{x-y})^b\) with \(x\) and \(b\) fixed. Then the transition becomes \(\displaystyle \mathrm{dp'}[x+a][a]\leftarrow \binom{x+a}{a}\sum_{b=1}^a \left\{ {a \atop b} \right\}\mathrm{coef}[x][b]\).

The number of sequences where \(B_i\neq \varnothing\) for all \(i\) is \(\sum_y \mathrm{dp'}[N][y]\).

Finally, we consider the case where some indices may remain as the empty set. If the size of the set of indices that eventually become non-empty is \(i\), then the number of ways to choose them is \(\binom{N}{i}\), and the number of ways to construct within that set is \(\sum_y \mathrm{dp'}[i][y]\). Also, there is one way where all sets remain empty.

Thus, the answer is \(\displaystyle 1+\sum_{i=1}^N \binom{N}{i}\sum_y \mathrm{dp'}[i][y]\).

The time complexity is \(O(N^3)\).

N, mod = map(int, input().split())

S = [[0] * (N + 1) for i in range(N + 1)]
binom = [[0] * (N + 1) for i in range(N + 1)]
for n in range(N + 1):
    S[n][n] = 1
    binom[n][0] = 1
    if n != 0:
        S[n][1] = 1
    for k in range(2, n):
        S[n][k] = (S[n - 1][k - 1] + k * S[n - 1][k]) % mod
    for k in range(1, n + 1):
        binom[n][k] = (binom[n - 1][k - 1] + binom[n - 1][k]) % mod

pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod


dp = [[0] * (N + 1) for _ in range(N + 1)]

for n in range(1, N + 1):
    dp[n][n] = sum(S[n][k] for k in range(1, n + 1)) % mod

ans = 1
for n in range(1, N + 1):
    coef = [0] * (N - n + 1)
    for pre in range(1, n + 1):
        rem = n - pre
        res2 = (pow2[pre] - 1) * pow2[rem] % mod

        p = 1
        for block in range(1, N - n + 1):
            p = p * res2 % mod
            coef[block] += dp[n][pre] * p
            coef[block] %= mod

    for add in range(1, N - n + 1):
        val = 0
        for block in range(1, add + 1):
            val += S[add][block] * coef[block]
            val %= mod

        dp[n + add][add] += val * binom[n + add][add]
        dp[n + add][add] %= mod

    ans += sum(dp[n]) * binom[N][n]
    ans %= mod

print(ans)