#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int) x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define ROF(i, a, b) for(int i=(b-1); i>=(a); i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)
#define trav(x, y) for(auto&x:y)

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using pli=pair<ll, int>;
using vi=vector<int>;
using vl=vector<ll>;
using vpii=vector<pii>;

template<class T> inline bool ckmin(T&a, const T&b) {return b<a?a=b,1:0;}
template<class T> inline bool ckmax(T&a, const T&b) {return b>a?a=b,1:0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl='\n';
const int mxN=401;
int MOD=1e9+7;
const ll infLL=1e18;
const ld eps=1e-6;

struct mint {
    int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint() { v = 0; }
    mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0) v += MOD; }
    friend bool operator==(const mint& a, const mint& b) { 
        return a.v == b.v; }
    friend bool operator!=(const mint& a, const mint& b) { 
        return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) { 
        return a.v < b.v; }
    mint& operator+=(const mint& m) { 
        if ((v += m.v) >= MOD) v -= MOD; 
        return *this; }
    mint& operator-=(const mint& m) { 
        if ((v -= m.v) < 0) v += MOD; 
        return *this; }
    mint& operator*=(const mint& m) { 
        v = int((ll)v*m.v%MOD); return *this; }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }
    friend mint pow(mint a, ll p) {
        mint ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; }
    friend mint inv(const mint& a) { assert(a.v != 0); 
        return pow(a,MOD-2); }
    mint operator-() const { return mint(-v); }
    mint& operator++() { return *this += 1; }
    mint& operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
};

vector<mint> invs, fac, ifac; // make sure to convert to LL before doing any multiplications ...
void genFac(int SZ) {
    invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ); vi Invs(SZ);
    Invs[1] = 1; invs[1] = fac[0] = ifac[0] = 1; 
    FOR(i,2,SZ) Invs[i] = int(MOD-(ll)MOD/i*Invs[MOD%i]%MOD), invs[i] = mint(Invs[i]);
    FOR(i,1,SZ) {
        fac[i] = fac[i-1]*i;
        ifac[i] = ifac[i-1]*invs[i];
    }
}

mint choose(int n, int k) {
    if(k>n) return 0;
    return fac[n]*ifac[n-k]*ifac[k];
}

int n; 
mint dp[3][mxN][mxN][2];
//dp[#ofperson][people left alive][position of person][increase or decrease]
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    cin >> MOD;
    dp[1][1][1][1]=1;
    FOR(i, 2, n+1){
        FOR(j, 1, i+1) FOR(k, 1, j+1) dp[i%3][j][k][0]=dp[i%3][j][k][1]=0;
        FOR(j, 1, i){//iterate on people alive in last spot
            vector<vector<mint>> psum(2, vector<mint>(j+1));
            FOR(k, 1, j+1){ //position of last guy
                psum[0][k]=psum[0][k-1]+dp[(i+2)%3][j][k][0];
                psum[1][k]=psum[1][k-1]+dp[(i+2)%3][j][k][1];
            }
            // this transition is adding normally
            FOR(k, 1, j+2){
                dp[i%3][j+1][k][1]+=psum[1][j]-psum[1][k-1];
                dp[i%3][j+1][k][0]+=psum[1][k-1]+psum[0][k-1];
            }
        }
        FOR(j, 1, i-1){
            mint tot=0;
            FOR(k, 1, j+1){
                tot+=dp[(i+1)%3][j][k][0]+dp[(i+1)%3][j][k][1];
            }
            FOR(k, 1, j+2){
                dp[i%3][j+1][k][1]+=tot;
            }
        }
    }
    mint res=0;
    FOR(j, 1, n+1){
        FOR(k, 1, j+1){
            res+=dp[n%3][j][k][0]+dp[n%3][j][k][1]; 
        }
    }
    cout << res.v << nl;
}

### Prompt

Please formulate a cpp solution to the following problem:

There are n computers in a row, all originally off, and Phoenix wants to turn all of them on. He will manually turn on computers one at a time. At any point, if computer i-1 and computer i+1 are both on, computer i (2 ≤ i ≤ n-1) will turn on automatically if it is not already on. Note that Phoenix cannot manually turn on a computer that already turned on automatically.

If we only consider the sequence of computers that Phoenix turns on manually, how many ways can he turn on all the computers? Two sequences are distinct if either the set of computers turned on manually is distinct, or the order of computers turned on manually is distinct. Since this number may be large, please print it modulo M.

Input

The first line contains two integers n and M (3 ≤ n ≤ 400; 10^8 ≤ M ≤ 10^9) — the number of computers and the modulo. It is guaranteed that M is prime.

Output

Print one integer — the number of ways to turn on the computers modulo M.

Examples

Input


3 100000007


Output


6


Input


4 100000007


Output


20


Input


400 234567899


Output


20914007

Note

In the first example, these are the 6 orders in which Phoenix can turn on all computers: 

  * [1,3]. Turn on computer 1, then 3. Note that computer 2 turns on automatically after computer 3 is turned on manually, but we only consider the sequence of computers that are turned on manually. 
  * [3,1]. Turn on computer 3, then 1. 
  * [1,2,3]. Turn on computer 1, 2, then 3. 
  * [2,1,3] 
  * [2,3,1] 
  * [3,2,1] 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int) x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define ROF(i, a, b) for(int i=(b-1); i>=(a); i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)
#define trav(x, y) for(auto&x:y)

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using pli=pair<ll, int>;
using vi=vector<int>;
using vl=vector<ll>;
using vpii=vector<pii>;

template<class T> inline bool ckmin(T&a, const T&b) {return b<a?a=b,1:0;}
template<class T> inline bool ckmax(T&a, const T&b) {return b>a?a=b,1:0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl='\n';
const int mxN=401;
int MOD=1e9+7;
const ll infLL=1e18;
const ld eps=1e-6;

struct mint {
    int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint() { v = 0; }
    mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0) v += MOD; }
    friend bool operator==(const mint& a, const mint& b) { 
        return a.v == b.v; }
    friend bool operator!=(const mint& a, const mint& b) { 
        return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) { 
        return a.v < b.v; }
    mint& operator+=(const mint& m) { 
        if ((v += m.v) >= MOD) v -= MOD; 
        return *this; }
    mint& operator-=(const mint& m) { 
        if ((v -= m.v) < 0) v += MOD; 
        return *this; }
    mint& operator*=(const mint& m) { 
        v = int((ll)v*m.v%MOD); return *this; }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }
    friend mint pow(mint a, ll p) {
        mint ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; }
    friend mint inv(const mint& a) { assert(a.v != 0); 
        return pow(a,MOD-2); }
    mint operator-() const { return mint(-v); }
    mint& operator++() { return *this += 1; }
    mint& operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
};

vector<mint> invs, fac, ifac; // make sure to convert to LL before doing any multiplications ...
void genFac(int SZ) {
    invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ); vi Invs(SZ);
    Invs[1] = 1; invs[1] = fac[0] = ifac[0] = 1; 
    FOR(i,2,SZ) Invs[i] = int(MOD-(ll)MOD/i*Invs[MOD%i]%MOD), invs[i] = mint(Invs[i]);
    FOR(i,1,SZ) {
        fac[i] = fac[i-1]*i;
        ifac[i] = ifac[i-1]*invs[i];
    }
}

mint choose(int n, int k) {
    if(k>n) return 0;
    return fac[n]*ifac[n-k]*ifac[k];
}

int n; 
mint dp[3][mxN][mxN][2];
//dp[#ofperson][people left alive][position of person][increase or decrease]
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    cin >> MOD;
    dp[1][1][1][1]=1;
    FOR(i, 2, n+1){
        FOR(j, 1, i+1) FOR(k, 1, j+1) dp[i%3][j][k][0]=dp[i%3][j][k][1]=0;
        FOR(j, 1, i){//iterate on people alive in last spot
            vector<vector<mint>> psum(2, vector<mint>(j+1));
            FOR(k, 1, j+1){ //position of last guy
                psum[0][k]=psum[0][k-1]+dp[(i+2)%3][j][k][0];
                psum[1][k]=psum[1][k-1]+dp[(i+2)%3][j][k][1];
            }
            // this transition is adding normally
            FOR(k, 1, j+2){
                dp[i%3][j+1][k][1]+=psum[1][j]-psum[1][k-1];
                dp[i%3][j+1][k][0]+=psum[1][k-1]+psum[0][k-1];
            }
        }
        FOR(j, 1, i-1){
            mint tot=0;
            FOR(k, 1, j+1){
                tot+=dp[(i+1)%3][j][k][0]+dp[(i+1)%3][j][k][1];
            }
            FOR(k, 1, j+2){
                dp[i%3][j+1][k][1]+=tot;
            }
        }
    }
    mint res=0;
    FOR(j, 1, n+1){
        FOR(k, 1, j+1){
            res+=dp[n%3][j][k][0]+dp[n%3][j][k][1]; 
        }
    }
    cout << res.v << nl;
}

```