This approach is considerably harder to come up with if you are not used to it (in my opinion), but once understood, the algebraic manipulation and implementation are simpler.

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\). Let this count be \(C_n\).

During the process of operations, there is a partial order: “the operation choosing \(S_1\) must always be performed before the operation choosing \(S_2\),” and this partial order forms a DAG. We would like to fix the sets with in-degree \(0\) in this DAG (that is, those that can be operated on first) and count for each choice, but it is difficult to count directly. Instead, we use inclusion-exclusion.

Fix a non-empty subset of the sets designated as having in-degree \(0\). Let \(a\) be the number of sets and \(s\) be the total number of indices contained across all these sets. The number of ways to partition \(s\) indices into \(a\) non-empty sets is \(\left\{{s \atop a} \right\}\).

For each set, it must contain its own indices. It cannot contain indices belonging to the other chosen in-degree-\(0\) sets. Each set can freely include any of the remaining \(n-s\) indices. Thus, the number of ways to determine the operation sets for the chosen \(a\) sets is \(2^{a(n-s)}\).

For the remaining \(n-s\) indices, the same problem remains independently. Thus, by inclusion-exclusion,

\[C_n=\sum_{s=1}^n\binom{n}{s}C_{n-s}\sum_{a=1}^s(-1)^{a+1}\left\{{s \atop a} \right\}2^{a(n-s)}\]

This formula can be computed directly in \(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 * N + 1)
for i in range(1, N * N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod


C = [0] * (N + 1)
C[0] = 1
ans = 1
for n in range(1, N + 1):
    for s in range(1, n + 1):
        tmp = 0
        sgn = 1
        for a in range(1, s + 1):
            tmp += sgn * S[s][a] * pow2[a * (n - s)]
            tmp %= mod
            sgn = -sgn
        C[n] += binom[n][s] * C[n - s] % mod * tmp
        C[n] %= mod
    ans += binom[N][n] * C[n]
    ans %= mod

print(ans)