全ての要素が \(0\) でないような \(A\) の個数を数えられれば元の問題の答えは dp で簡単にわかるので，これを数えることにします．

操作を逆順に見ると，「すべての \(i=l,\ldots,r\) に対して \(A_i\in \{0,r(r-1)/2+l\}\) であるような \(l,r\) を選び，\(A_i=0\) とする（これを「\(r(r-1)/2+l\) を消す」と呼ぶことにする）」を繰り返して最終的に全部の要素を \(0\) にできるような数列が条件を満たします．

この逆順の操作において，「\((l_1,r_1)\) は必ず \((l_2,r_2)\) の先に行わなければならない」という順序関係が存在し，この順序関係は DAG になっています．最後の \(1\) 手として消せる値（DAG における出次数 \(0\)）の集合を \(S\) としたとき，\(S\) ごとに条件を満たす \(A\) を数え上げることを考えたいですが，直接数えるのは難しいです．

そこで，\(S\) の非空な部分集合 \(T\) すべてについて \((-1)^{|T|-1}\) を足すことを考えます．

\(T\) を固定すると簡単に数えることができます．\(T\) に含まれる値を並べると，互いに干渉しない区間が横に並んでいます．\(T\) に含まれない部分は，単にこの小さい区間内で全部消せる状態になっています．

これで dp ができます．\(\mathrm{dp}1[i]\) を「作ることができる長さ \(i\) の \(A\) のうち，すべての要素が非零なものの個数」，\(\mathrm{dp}2[i]\) を「作ることができる長さ \(i\) の \(A\) のうち，すべての要素が非零であり，かつ場所 \(i\) は \(T\) に含まれる数であるものすべてに対する \((-1)^{|T|-1}\) の総和」とします．

最も複雑な \(\mathrm{dp}2[l]\) から \(\mathrm{dp}2[r]\) への遷移は，

• \(l,r\) の値が同じ場合：\(l\) と \(r\) の間を消せるので \(\mathrm{dp}1[r-1-l]\) 倍
• \(l,r\) の値が異なる場合：\(l\) の値の右端，および \(r\) の値の左端が \([l,r]\) 間にあるので \((r-l)^2\) 倍，さらに \(l\) と \(r\) の間を消せるので \(\mathrm{dp}1[r-1-l]\) 倍，さらに値の種類数が増えるので \(-1\) 倍

になります．

計算量は \(O(N^2)\) です．

n, mod = map(int, input().split())
dp1, dp2, ans = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
dp1[0] = 1
ans[0] = 1
for i in range(1, n + 1):
    dp2[i] = dp1[i - 1] * i
    for j in range(i):
        dp1[i] += dp2[j + 1] * (i - j) % mod * dp1[i - j - 1] % mod
        dp2[i] += dp2[j] * (1 - (i - j) * (i - j)) % mod * dp1[i - j - 1] % mod
        ans[i] += ans[j] * dp1[i - j - 1] % mod
    ans[i] += dp1[i]
    dp1[i] %= mod
    dp2[i] %= mod
    ans[i] %= mod
print(ans[n])