慣れていないと発想はこちらの方がかなり難しい（と私は思います）が，理解できれば式変形や実装が楽な方針です．

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

• 長さ \(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\) であるようなものだけを考えることにします．この個数を \(C_n\) とします．

操作の過程において，「\(S_1\) を選ぶ操作は必ず \(S_2\) の先に行わなければならない」という順序関係が存在し，この順序関係は DAG になっています．この DAG において，入次数が \(0\) であるような集合（最初に操作を行うことができる集合）たちを決め打ってそれぞれで数え上げることを考えたいですが，直接数えるのは難しいです．そこで包除原理で数えます．

入次数 \(0\) であると指定する集合の非空な部分集合を一つ決め打ちます．集合の数を \(a\)，各集合に含まれる添え字の個数の総和を \(s\) とします．\(s\) 個の添え字を \(a\) 個の非空な集合に分割する方法は \(\left\{{s \atop a} \right\}\) 通りです．

それぞれの集合について，自分自身に属する添え字は必ず含まなければなりません．また，選んだ入次数 \(0\) の集合どうしの添え字を含むことはできません．各集合は，残りの \(n-s\) 個の添え字を自由に追加できます．よって，選んだ \(a\) 個の集合に対して，対応する操作集合の決め方は \(2^{a(n-s)}\) 通りです．

残りの \(n-s\) 個の添え字については，同じ問題が独立に残ります．したがって包除原理より

\[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)}\]

です．この式はそのまま \(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)