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

//======================
//      MODULE
//======================
struct ModInt;
vector<ModInt> inverse();

using ModType = long long; // set Type
struct ModInt
{
    static inline vector<ModInt> precalcInverse;
    static inline map<ModType, ModInt> cache;
    static void precalc()
    {
        precalcInverse = inverse();
    }

    static inline ModType mod = 1e9 + 7; // Set this value
    ModType val;
    ModInt(ModType v = 0) : val(v % mod) { }
    static void setMod(ModType m)
    {
        mod = m;
        if(precalcInverse.size() > 0)
        {
            precalcInverse = inverse();
        }
    }
    ModInt operator-() const
    {
        return ModInt(val ? mod - val : val);
    }
    ModInt &operator+=(ModInt a)
    {
        if ((val += a.val) >= mod) val -= mod;
        return *this;
    }
    ModInt &operator-=(ModInt a)
    {
        if ((val -= a.val) < 0) val += mod;
        return *this;
    }
    ModInt &operator*=(ModInt a)
    {
        val = (val * a.val) % mod;
        return *this;
    }
    ModInt &operator/=(ModInt a)
    {
        long long toCache=a.val;
        if(cache.find(toCache)!=cache.end()){
            *this *= cache[a.val];
            return *this;
        }
        if(precalcInverse.size() > a.val)
        {
            *this *= precalcInverse[a.val];
            return *this;
        }
        ModType u = 1, v = a.val, s = 0, t = mod;
        while (v)
        {
            ModType q = t / v;
            swap(s -= u * q, u);
            swap(t -= v * q, v);
        }
        a.val = (s < 0 ? s + mod : s);
        val /= t;
        cache[toCache]=a;
        return (*this) *= a;
    }
    ModInt inv() const
    {
        return ModInt(1) /= (*this);
    }
    bool operator<(ModInt x) const
    {
        return val < x.val;
    }
};
ostream &operator<<(ostream &os, ModInt a)
{
    os << a.val;
    return os;
}
ModInt operator+(ModInt a, ModInt b)
{
    return a += b;
}
ModInt operator-(ModInt a, ModInt b)
{
    return a -= b;
}
ModInt operator*(ModInt a, ModInt b)
{
    return a *= b;
}
ModInt operator/(ModInt a, ModInt b)
{
    return a /= b;
}
ModInt pow(ModInt a, ModType e)
{
    ModInt x(1);
    for (; e > 0; e /= 2)
    {
        if (e % 2 == 1) x *= a;
        a *= a;
    }
    return x;
}
// compute inv[1], inv[2], ..., inv[mod-1] in O(n) time
vector<ModInt> inverse()
{
    ModType mod = ModInt::mod;
    vector<ModInt> inv(mod);
    inv[1].val = 1;
    for (ModType a = 2; a < mod; ++a)
        inv[a] = inv[mod % a] * ModInt(mod - mod / a);
    return inv;
}
ModInt stringToModInt(string s)
{
    ModType val = 0;
    for (int i = 0; i < s.size(); ++i)
        val = (val * 10 + (s[i] - '0')) % ModInt::mod;
    return ModInt(val);
}

//======================
//      Combinatorics
//======================

using CombType = ModInt; // set Type
struct Combinatorics
{
    vector<CombType> factorial = {1};
    int nPrecalcFactorial = 0;

    void precalcFactorial(int n)
    {
        CombType sum = factorial[nPrecalcFactorial];
        for(long long i = nPrecalcFactorial + 1; i <= n; i++)
        {
            sum *= i;
            factorial.push_back(sum);
        }
        nPrecalcFactorial = n;
    }

    CombType binomial(int n, int k)
    {
        CombType res = 1;
        if(nPrecalcFactorial < n)
        {
            for (int i = 0; i < k; i++)
            {
                res = res * (n - i) / (i + 1);
            }
        }
        else
        {
            res = factorial[n];
            res /= factorial[k];
            res /= factorial[n - k];
        }
        return res;
    }

};

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "[";
    for (int i = 0; i < v.size(); ++i)
    {
        os << v[i];
        if (i != v.size() - 1)
            os << ", ";
    }
    os << "]\n";
    return os;
}

template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p)
{
    os << "[";
    os << p.first;
    os << ", ";
    os << p.second;
    os << "]";
    return os;
}

#ifndef ONLINE_JUDGE
#define debug(x) cout << (#x) << " is " << (x) << endl
#else
#define debug(...) 42
#endif

long long cntTest(int n, vector<bool>& tst, vector<int>& sol)
{
    bool full = true;
    long long sum = 0;
    for(int i = 0; i < n; i++)
    {
        if(tst[i] == false)
        {
            full = false;
            vector<bool> newtst = tst;
            newtst[i] = true;
            if(i - 2 >= 0)
                if(newtst[i] && newtst[i - 2])
                    newtst[i - 1] = true;
            if(i + 2 < n)
                if(newtst[i] && newtst[i + 2])
                    newtst[i + 1] = true;

            sol.push_back(i);
            sum += cntTest(n, newtst, sol);
            sol.erase(sol.end() - 1);
        }
    }
    if(full)
    {
        debug(sol);
        sum++;
    }
    return sum;
}


int solve()
{
    long long n, mod;
    cin >> n >> mod;
    ModInt::setMod(mod);
    //ModInt::precalc();
    Combinatorics comb;
    comb.precalcFactorial(405);
    // test
    /*for(int i = 1; i <= 5; ++i)
    {
        vector<bool> tst(i, false);
        vector<int> sol;
        long long solcnt=cntTest(i, tst, sol);
        cout << "------------------------------------------" << endl;
        cout << i << ": " << solcnt << endl;
        cout << "------------------------------------------" << endl;
    }*/

    /*    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0)); // solve for n with exactly k steps;
        dp[0][0] = 1;
        dp[1][1] = 1;
        dp[2][2] = 2;
        for(long long i = 3; i <= n; i++)
        {
            for(long long j = 2; j <= n; j++)
            {
                dp[i][j] += dp[i - 1][j-1]*j;
                dp[i][j] += dp[i - 2][j-1]*j;
            }
        }
        long long sol=0;
        cout << dp[n];
        for(long long i = 0; i <= n; i++)
        {
            sol+=dp[n][i];
        }
        cout << sol << "\n";
    */
    debug("Precalc Done");
    vector<vector<ModInt>> dp(n + 1, vector<ModInt>(n + 1, 0)); // solve for n with exactly k steps;
    dp[0][0] = 1;
    dp[1][1] = 1;
    for(int i = 2; i <= n; i++)
    {
        dp[i][i] = dp[i - 1][i - 1] * 2;
    }
    vector<ModInt> pow2(405);
    pow2[0]=1;
    for(int i = 1; i <= n; i++)
    {
        pow2[i] = pow2[i - 1] * 2;
    }
    debug("Pows done");
    for(long long i = 1; i <= n; i++)
    {
        for(long long j = 0; j <= i; j++)
        {
            for(long long k = 1; k+1+i <= n; k++)
            {
                dp[i+1+k][j+k] += dp[i][j] * comb.binomial(j+k,k)*pow2[k-1];
            }
        }
    }
    ModInt sol = 0;
    debug(dp);
    for(long long i = 0; i <= n; i++)
    {
        sol += dp[n][i];
    }
    cout << sol << "\n";


    return 0;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("a.out","w",stdout); // console output is better (in most cases)
#else
    // add i/o method of specific testing system
#endif
    {
        solve();
    }
    return 0;
}

### Prompt

Please create a solution in Cpp 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;

//======================
//      MODULE
//======================
struct ModInt;
vector<ModInt> inverse();

using ModType = long long; // set Type
struct ModInt
{
    static inline vector<ModInt> precalcInverse;
    static inline map<ModType, ModInt> cache;
    static void precalc()
    {
        precalcInverse = inverse();
    }

    static inline ModType mod = 1e9 + 7; // Set this value
    ModType val;
    ModInt(ModType v = 0) : val(v % mod) { }
    static void setMod(ModType m)
    {
        mod = m;
        if(precalcInverse.size() > 0)
        {
            precalcInverse = inverse();
        }
    }
    ModInt operator-() const
    {
        return ModInt(val ? mod - val : val);
    }
    ModInt &operator+=(ModInt a)
    {
        if ((val += a.val) >= mod) val -= mod;
        return *this;
    }
    ModInt &operator-=(ModInt a)
    {
        if ((val -= a.val) < 0) val += mod;
        return *this;
    }
    ModInt &operator*=(ModInt a)
    {
        val = (val * a.val) % mod;
        return *this;
    }
    ModInt &operator/=(ModInt a)
    {
        long long toCache=a.val;
        if(cache.find(toCache)!=cache.end()){
            *this *= cache[a.val];
            return *this;
        }
        if(precalcInverse.size() > a.val)
        {
            *this *= precalcInverse[a.val];
            return *this;
        }
        ModType u = 1, v = a.val, s = 0, t = mod;
        while (v)
        {
            ModType q = t / v;
            swap(s -= u * q, u);
            swap(t -= v * q, v);
        }
        a.val = (s < 0 ? s + mod : s);
        val /= t;
        cache[toCache]=a;
        return (*this) *= a;
    }
    ModInt inv() const
    {
        return ModInt(1) /= (*this);
    }
    bool operator<(ModInt x) const
    {
        return val < x.val;
    }
};
ostream &operator<<(ostream &os, ModInt a)
{
    os << a.val;
    return os;
}
ModInt operator+(ModInt a, ModInt b)
{
    return a += b;
}
ModInt operator-(ModInt a, ModInt b)
{
    return a -= b;
}
ModInt operator*(ModInt a, ModInt b)
{
    return a *= b;
}
ModInt operator/(ModInt a, ModInt b)
{
    return a /= b;
}
ModInt pow(ModInt a, ModType e)
{
    ModInt x(1);
    for (; e > 0; e /= 2)
    {
        if (e % 2 == 1) x *= a;
        a *= a;
    }
    return x;
}
// compute inv[1], inv[2], ..., inv[mod-1] in O(n) time
vector<ModInt> inverse()
{
    ModType mod = ModInt::mod;
    vector<ModInt> inv(mod);
    inv[1].val = 1;
    for (ModType a = 2; a < mod; ++a)
        inv[a] = inv[mod % a] * ModInt(mod - mod / a);
    return inv;
}
ModInt stringToModInt(string s)
{
    ModType val = 0;
    for (int i = 0; i < s.size(); ++i)
        val = (val * 10 + (s[i] - '0')) % ModInt::mod;
    return ModInt(val);
}

//======================
//      Combinatorics
//======================

using CombType = ModInt; // set Type
struct Combinatorics
{
    vector<CombType> factorial = {1};
    int nPrecalcFactorial = 0;

    void precalcFactorial(int n)
    {
        CombType sum = factorial[nPrecalcFactorial];
        for(long long i = nPrecalcFactorial + 1; i <= n; i++)
        {
            sum *= i;
            factorial.push_back(sum);
        }
        nPrecalcFactorial = n;
    }

    CombType binomial(int n, int k)
    {
        CombType res = 1;
        if(nPrecalcFactorial < n)
        {
            for (int i = 0; i < k; i++)
            {
                res = res * (n - i) / (i + 1);
            }
        }
        else
        {
            res = factorial[n];
            res /= factorial[k];
            res /= factorial[n - k];
        }
        return res;
    }

};

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "[";
    for (int i = 0; i < v.size(); ++i)
    {
        os << v[i];
        if (i != v.size() - 1)
            os << ", ";
    }
    os << "]\n";
    return os;
}

template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p)
{
    os << "[";
    os << p.first;
    os << ", ";
    os << p.second;
    os << "]";
    return os;
}

#ifndef ONLINE_JUDGE
#define debug(x) cout << (#x) << " is " << (x) << endl
#else
#define debug(...) 42
#endif

long long cntTest(int n, vector<bool>& tst, vector<int>& sol)
{
    bool full = true;
    long long sum = 0;
    for(int i = 0; i < n; i++)
    {
        if(tst[i] == false)
        {
            full = false;
            vector<bool> newtst = tst;
            newtst[i] = true;
            if(i - 2 >= 0)
                if(newtst[i] && newtst[i - 2])
                    newtst[i - 1] = true;
            if(i + 2 < n)
                if(newtst[i] && newtst[i + 2])
                    newtst[i + 1] = true;

            sol.push_back(i);
            sum += cntTest(n, newtst, sol);
            sol.erase(sol.end() - 1);
        }
    }
    if(full)
    {
        debug(sol);
        sum++;
    }
    return sum;
}


int solve()
{
    long long n, mod;
    cin >> n >> mod;
    ModInt::setMod(mod);
    //ModInt::precalc();
    Combinatorics comb;
    comb.precalcFactorial(405);
    // test
    /*for(int i = 1; i <= 5; ++i)
    {
        vector<bool> tst(i, false);
        vector<int> sol;
        long long solcnt=cntTest(i, tst, sol);
        cout << "------------------------------------------" << endl;
        cout << i << ": " << solcnt << endl;
        cout << "------------------------------------------" << endl;
    }*/

    /*    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0)); // solve for n with exactly k steps;
        dp[0][0] = 1;
        dp[1][1] = 1;
        dp[2][2] = 2;
        for(long long i = 3; i <= n; i++)
        {
            for(long long j = 2; j <= n; j++)
            {
                dp[i][j] += dp[i - 1][j-1]*j;
                dp[i][j] += dp[i - 2][j-1]*j;
            }
        }
        long long sol=0;
        cout << dp[n];
        for(long long i = 0; i <= n; i++)
        {
            sol+=dp[n][i];
        }
        cout << sol << "\n";
    */
    debug("Precalc Done");
    vector<vector<ModInt>> dp(n + 1, vector<ModInt>(n + 1, 0)); // solve for n with exactly k steps;
    dp[0][0] = 1;
    dp[1][1] = 1;
    for(int i = 2; i <= n; i++)
    {
        dp[i][i] = dp[i - 1][i - 1] * 2;
    }
    vector<ModInt> pow2(405);
    pow2[0]=1;
    for(int i = 1; i <= n; i++)
    {
        pow2[i] = pow2[i - 1] * 2;
    }
    debug("Pows done");
    for(long long i = 1; i <= n; i++)
    {
        for(long long j = 0; j <= i; j++)
        {
            for(long long k = 1; k+1+i <= n; k++)
            {
                dp[i+1+k][j+k] += dp[i][j] * comb.binomial(j+k,k)*pow2[k-1];
            }
        }
    }
    ModInt sol = 0;
    debug(dp);
    for(long long i = 0; i <= n; i++)
    {
        sol += dp[n][i];
    }
    cout << sol << "\n";


    return 0;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("a.out","w",stdout); // console output is better (in most cases)
#else
    // add i/o method of specific testing system
#endif
    {
        solve();
    }
    return 0;
}

```