問題は次のように言い換えられます．

• 長さ \(N\) の集合の列 \(B=(\lbrace \rbrace,\lbrace \rbrace,\ldots,\lbrace \rbrace)\) がある．
• 「集合 \(S\subset \lbrace 1,2,\ldots,N\rbrace\) を選び，各 \(i\in S\) に対して \(B_i=S\) とする」という操作を繰り返すことができる
• 最終的な \(B\) は何通り？

以下では，すべての \(i\) について \(B_i\neq \varnothing\) であるようなものだけを考えることにします．

まず，集合の列 \(B\) が与えられたときに，それが操作によって作ることができるかという判定問題を考えます．これは操作を逆順に見ながら解くことができます．

• すでに取り除いた添字集合を管理する集合 \(I\) を用意する．はじめ，\(I=\varnothing\) である．
• 以下の操作 X を繰り返す．
  • 以下を満たす集合 \(S\) を一つ見つける．
    • 各 \(i\in S\) に対して，\(B_i=S\) または \(i\in I\) である．
    • \(i\notin I\) であるような \(i\in S\) が存在する
  • \(I\) を \(I\cup S\) で置き換える．
• 最終的に \(I=\lbrace 1,2,\ldots,N\rbrace\) とできれば，\(B\) は作ることができる．

このままだと，逆操作の列は複数通りあって数えにくいので，以下のようにして逆操作の列を一意にします．

• すでに取り除いた添字集合を管理する集合 \(I\) を用意する．はじめ，\(I=\varnothing\) である．
• 以下の操作 Y を繰り返す．
  • 以下を満たす集合 \(S\) をすべて列挙する．
    • 各 \(i\in S\) に対して，\(B_i=S\) または \(i\in I\) である．
    • \(i\notin I\) であるような \(i\in S\) が存在する
  • 列挙した集合を \(S_1,S_2,\ldots\) として，\(I\) を \(I\cup S_1\cup S_2\cup \ldots\) で置き換える．
• 最終的に \(I=\lbrace 1,2,\ldots,N\rbrace\) とできれば，\(B\) は作ることができる．

これにより，一意化された逆操作列の個数を数え上げればよいことになります．

\(j\) 回目の操作 Y 後の \(I\) を \(I_j\)， \(C_j=I_j\setminus I_{j-1}\) とします．\(I_{j-1}\) と \(C_j\) を決め打ったときに，ありうる \(\lbrace S_1,S_2,\ldots\rbrace \) の個数を考えます．

\(1\) 回目の操作については，\(S_1,S_2,\ldots\) は \(I_1\) の分割になります．

\(j\geq 2\) の場合，\(S_k\) に対して \(D_k=\lbrace i\in C_j\mid B_i=S_k\rbrace\) とすると，定義から \(D_1,D_2,\ldots\) は \(C_j\) の分割になります．\(D_k\) を決め打ったとき，\(S_k\) は以下を満たす必要があります．

• \(S_k\setminus D_k\) は \(I_{j-1}\) の部分集合
• \((S_k\setminus D_k)\cap C_{j-1}\) は非空

よって，\(S_k\) の個数は \(2^{|I_{j-1}|}-2^{|I_{j-1}|-|C_{j-1}|}\) です．

あとはこれを DP にします．

ここでは，最終的に非空になる添字集合を固定して数えることにします． \(\mathrm{dp'}[x][y]\) を「固定された \(x\) 個の添字について，操作 Y を何回か行った結果，\(|I|=x\)，直前に追加された集合の大きさが \(y\) であるようなものの個数」とします．

\(1\) 回目の操作だけで \(a\) 個すべてが取り除かれる場合，\(S_1,S_2,\ldots\) は \(a\) 個の添字の分割なので，\(\displaystyle \mathrm{dp'}[a][a]=\sum_{b=1}^a \left\{ {a \atop b} \right\}\) です（\(\left\{ {a \atop b} \right\}\) は第二種スターリング数）．

遷移について，現在 \(|I|=x, |C|=y\) であり，次に追加する集合のサイズを \(a\) とします． 最終的に使う \(x+a\) 個の添字を固定したとき，そのうち次の \(C\) として使う \(a\) 個の選び方は \(\binom{x+a}{a}\) 通りです．

また，\(C\) を \(b\) 個の集合 \(D_1,D_2,\ldots,D_b\) に分割するとしたとき，

• 次の \(C\) の選び方：\(\binom{x+a}{a}\) 通り
• \(C\) を \(b\) 個に分割する方法：\(\left\{ {a \atop b} \right\}\) 通り
• 各 \(D_k\) に対する \(S_k\) の決め方：\((2^x-2^{x-y})^b\) 通り

の積が係数にかかります．すなわち， \(\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]\) です．

この式をそのまま計算すると \(x,y,a,b\) の \(4\) 重ループになってしまいます．そこで，\(x,b\) を固定して先に \(\displaystyle \mathrm{coef}[x][b]=\sum_{y=1}^x\mathrm{dp'}[x][y](2^x-2^{x-y})^b\) を計算しておきます．すると，遷移は \(\displaystyle \mathrm{dp'}[x+a][a]\leftarrow \binom{x+a}{a}\sum_{b=1}^a \left\{ {a \atop b} \right\}\mathrm{coef}[x][b]\) と書けます．

すべての \(i\) について \(B_i\neq \varnothing\) であるようなものの個数は \(\sum_y \mathrm{dp'}[N][y]\) です．

最後に，空集合のまま残る添字があってもよい場合を考えます． 最終的に非空になる添字集合のサイズを \(i\) とすると，その選び方は \(\binom{N}{i}\) 通りであり，その内部での作り方は \(\sum_y \mathrm{dp'}[i][y]\) 通りです． また，すべて空集合である場合が \(1\) 通りあります．

したがって答えは \(\displaystyle 1+\sum_{i=1}^N \binom{N}{i}\sum_y \mathrm{dp'}[i][y]\) です．

計算量は \(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)