/*
  Created by: Amit Kumar at 23:25 on 04 May 21
*/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define db(...)
#endif
using namespace std;

#define ll long long
#define S(x, n) memset(x, n, sizeof(x));
#define pb(x) emplace_back(x)
#define all(x) x.begin(), x.end()
#define NIL -1

const long long MAXN = 400 + 5;
long long mod = 1e9 + 7;

vector<ll> fact(MAXN);
vector<ll> inv_fact(MAXN);
vector<ll> p2(MAXN);

long long power(long long x, long long y)
{
    long long res = 1;
    x = x % mod;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % mod;
        y = y >> 1;
        x = (x * x) % mod;
    }
    return res;
}

void build_fact()
{
    fact[0] = 1;
    p2[0] = 1;
    for (ll i = 1; i < MAXN; i++)
    {
        fact[i] = (i * fact[i - 1]) % mod;
        p2[i] = (2 * p2[i - 1]) % mod;
    }
    inv_fact[MAXN - 1] = power(fact[MAXN - 1], mod - 2);
    for (ll i = MAXN - 2; i >= 0; i--)
    {
        inv_fact[i] = ((i + 1) * inv_fact[i + 1]) % mod;
    }
}

ll ncr(ll n, ll r)
{
    static bool built = false;
    if (!built)
    {
        build_fact();
        built = true;
    }
    if (n < r)
        return 0;
    if (n < 0 || r < 0)
        return 0;
    return (((fact[n] * inv_fact[r]) % mod) * (inv_fact[n - r])) % mod;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &A);

void solve()
{
    ll n;
    cin >> n >> mod;
    vector<vector<ll>> dp(n + 2, vector<ll>(n + 1));
    // i is index 1 based
    // cnt is count of manual ons
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++)
        for (int cnt = 0; cnt <= i; cnt++)
            for (int len = 1; len <= n; len++)
                if (i + len <= n)
                    dp[i + len + 1][cnt + len] = (dp[i + len + 1][cnt + len] + ((dp[i][cnt] * ncr(cnt + len, len)) % mod) * p2[len - 1] % mod) % mod;

    ll ans = 0;
    for (int i = 0; i <= n; i++)
        ans = (ans + dp[n + 1][i]) % mod;
    cout << ans << "\n";
}
int32_t main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    auto started = std::chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    //cin >> t;
    for (int I = 1; I <= t; I++)
    {
#ifdef LOCAL
        cerr << "TestCase " << I << "\n";
#endif
        solve();
    }
#ifdef LOCAL
    auto done = std::chrono::high_resolution_clock::now();
    cerr << "Time = " << std::chrono::duration_cast<std::chrono::milliseconds>(done - started).count() << " ms\n";
#endif
    return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &A)
{
    for (int i = 0; i < A.size(); i++)
        is >> A[i];
    return is;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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
/*
  Created by: Amit Kumar at 23:25 on 04 May 21
*/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define db(...)
#endif
using namespace std;

#define ll long long
#define S(x, n) memset(x, n, sizeof(x));
#define pb(x) emplace_back(x)
#define all(x) x.begin(), x.end()
#define NIL -1

const long long MAXN = 400 + 5;
long long mod = 1e9 + 7;

vector<ll> fact(MAXN);
vector<ll> inv_fact(MAXN);
vector<ll> p2(MAXN);

long long power(long long x, long long y)
{
    long long res = 1;
    x = x % mod;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % mod;
        y = y >> 1;
        x = (x * x) % mod;
    }
    return res;
}

void build_fact()
{
    fact[0] = 1;
    p2[0] = 1;
    for (ll i = 1; i < MAXN; i++)
    {
        fact[i] = (i * fact[i - 1]) % mod;
        p2[i] = (2 * p2[i - 1]) % mod;
    }
    inv_fact[MAXN - 1] = power(fact[MAXN - 1], mod - 2);
    for (ll i = MAXN - 2; i >= 0; i--)
    {
        inv_fact[i] = ((i + 1) * inv_fact[i + 1]) % mod;
    }
}

ll ncr(ll n, ll r)
{
    static bool built = false;
    if (!built)
    {
        build_fact();
        built = true;
    }
    if (n < r)
        return 0;
    if (n < 0 || r < 0)
        return 0;
    return (((fact[n] * inv_fact[r]) % mod) * (inv_fact[n - r])) % mod;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &A);

void solve()
{
    ll n;
    cin >> n >> mod;
    vector<vector<ll>> dp(n + 2, vector<ll>(n + 1));
    // i is index 1 based
    // cnt is count of manual ons
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++)
        for (int cnt = 0; cnt <= i; cnt++)
            for (int len = 1; len <= n; len++)
                if (i + len <= n)
                    dp[i + len + 1][cnt + len] = (dp[i + len + 1][cnt + len] + ((dp[i][cnt] * ncr(cnt + len, len)) % mod) * p2[len - 1] % mod) % mod;

    ll ans = 0;
    for (int i = 0; i <= n; i++)
        ans = (ans + dp[n + 1][i]) % mod;
    cout << ans << "\n";
}
int32_t main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    auto started = std::chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    //cin >> t;
    for (int I = 1; I <= t; I++)
    {
#ifdef LOCAL
        cerr << "TestCase " << I << "\n";
#endif
        solve();
    }
#ifdef LOCAL
    auto done = std::chrono::high_resolution_clock::now();
    cerr << "Time = " << std::chrono::duration_cast<std::chrono::milliseconds>(done - started).count() << " ms\n";
#endif
    return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &A)
{
    for (int i = 0; i < A.size(); i++)
        is >> A[i];
    return is;
}
```