// Parece que aún tengo aliados en el olimpo

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

// Based on tourist template: https://codeforces.com/contest/1423/submission/94770723
int mod = 1e9 + 7;

class Mint {
private:
  int value;

  template <typename T>
  static T inverse (T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
      T t = m / a;
      m -= t * a; swap(a, m);
      u -= t * v; swap(u, v);
    }
    assert(m == 1);
    return u;
  }

public:

  constexpr Mint (): value(0) {}

  template <class U>
  Mint (const U& x) { value = normalize(x); }

  template <class U>
  static int normalize (const U& x) {
    int ret;
    if (-mod <= x and x < mod) ret = x;
    else ret = x % mod;
    if (ret < 0) ret += mod;
    return ret;
  }

  static void set_mod (int new_mod) { mod = new_mod; }

  const int& operator ()() const { return value; }

  Mint& operator += (const Mint& other) { if ((value += other.value) >= mod) value -= mod; return *this; }
  Mint& operator -= (const Mint& other) { if ((value -= other.value) < 0) value += mod; return *this; }
  Mint& operator ++ () { return *this += 1; }
  Mint& operator -- () { return *this -= 1; }
  Mint operator ++ (int) { Mint ret(*this); *this += 1; return ret; }
  Mint operator -- (int) { Mint ret(*this); *this -= 1; return ret; }
  Mint operator - () const { return Mint(-value); }
  Mint& operator *= (const Mint& other) { value = normalize(1LL * value * other.value); return *this; }
  Mint& operator /= (const Mint& other) { return *this *= Mint(inverse(other.value, mod)); }

  friend bool operator == (const Mint& lhs, const Mint& rhs) { return lhs.value == rhs.value; }
  template <class U>
  friend bool operator == (const Mint& lhs, U rhs) { return lhs == Mint(rhs); }
  template <class U>
  friend bool operator == (U lhs, const Mint& rhs) { return Mint(lhs) == rhs; }

  friend bool operator != (const Mint& lhs, const Mint& rhs) { return not (lhs == rhs); }
  template <class U>
  friend bool operator != (const Mint& lhs, U rhs) { return not (lhs == rhs); }
  template <class U>
  friend bool operator != (U lhs, const Mint& rhs) { return not (lhs == rhs); }

  friend bool operator < (const Mint& lhs, const Mint& rhs) { return lhs.value < rhs.value; }

  friend Mint operator + (const Mint& lhs, const Mint& rhs) { return Mint(lhs) += rhs; }
  template <class U>
  friend Mint operator + (const Mint& lhs, U rhs) { return Mint(lhs) += rhs; }
  template <class U>
  friend Mint operator + (U lhs, const Mint& rhs) { return Mint(lhs) += rhs; }

  friend Mint operator - (const Mint& lhs, const Mint& rhs) { return Mint(lhs) -= rhs; }
  template <class U>
  friend Mint operator - (const Mint& lhs, U rhs) { return Mint(lhs) -= rhs; }
  template <class U>
  friend Mint operator - (U lhs, const Mint& rhs) { return Mint(lhs) -= rhs; }

  friend Mint operator * (const Mint& lhs, const Mint& rhs) { return Mint(lhs) *= rhs; }
  template <class U>
  friend Mint operator * (const Mint& lhs, U rhs) { return Mint(lhs) *= rhs; }
  template <class U>
  friend Mint operator * (U lhs, const Mint& rhs) { return Mint(lhs) *= rhs; }

  friend Mint operator / (const Mint& lhs, const Mint& rhs) { return Mint(lhs) /= rhs; }
  template <class U>
  friend Mint operator / (const Mint& lhs, U rhs) { return Mint(lhs) /= rhs; }
  template <class U>
  friend Mint operator / (U lhs, const Mint& rhs) { return Mint(lhs) /= rhs; }

  friend Mint power (Mint a, ll b) {
    assert(b >= 0);
    Mint ret = 1;
    while (b != 0) {
      if (b & 1) ret *= a;
      a *= a;
      b >>= 1;
    }
    return ret;
  }

  friend std::ostream& operator << (std::ostream& stream, const Mint& number) { return stream << number(); }

  friend std::istream& operator >> (std::istream& stream, Mint& number) {
    ll x;
    stream >> x;
    number.value = Mint::normalize(x);
    return stream;
  }

};

int check (int n) {
  vi perm(n);
  iota(all(perm), 0);
  int cnt = 0;
  do {
    vi vis(n, 0);
    bool ok = true;
    for (int pi: perm) {
      if (vis[pi]) ok = false;
      vis[pi] = 1;
      for (int i = 1; i + 1 < n; i++) {
        if (vis[i - 1] and vis[i + 1]) vis[i] = 1;
      }
    }
    cnt += ok;
  } while (next_permutation(all(perm)));
  return cnt;
};

// Modular Number Theory
struct MNT {
  vector <Mint> fact;
  vector <Mint> inv_fact;

  void preprocess_factorial (int n) {
    fact.resize(n + 1);
    inv_fact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
    ll z = 1;
    inv_fact[n] = 1 / fact[n];
    for (int i = n - 1; i >= 0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1);
  }

  Mint comb (int a, int b) {
    if (a < b) return 0;
    return fact[a] * inv_fact[b] * inv_fact[a - b];
  }
};

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  /*
  for (int z = 1; z <= 9; z++) cout << z << ' ' << check(z) << endl; 
  return 0;
  */
  int n, mod;
  cin >> n >> mod;
  Mint::set_mod(mod);
  MNT mnt;
  mnt.preprocess_factorial(n + 1);
  vector <Mint> z(n + 1);
  z[1] = 1;
  for (int i = 2; i <= n; i++) {
    z[i] = z[i - 1] * 2;
  }
  vector <vector <Mint>> dp(n, vector <Mint> (n + 1, 0));
  vector <vi> vis(n, vi(n + 1, 0));
  function <Mint(int,int)> rec = [&] (int pos, int total) -> Mint {
    if (pos == n) return 0;
    if (pos == n + 1) return mnt.fact[total];
    if (vis[pos][total]) return dp[pos][total];
    vis[pos][total] = 1;
    Mint ret = 0;
    for (int len = 1; pos + len - 1 <= n - 1; len++) {
      Mint add = z[len] * rec(pos + len + 1, total + len) / mnt.fact[len];
      ret += add;
    }
    return dp[pos][total] = ret;
  };
  cout << rec(0, 0) << '\n';
  return (0);
}

### Prompt

Develop a solution in CPP 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
// Parece que aún tengo aliados en el olimpo

#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

// Based on tourist template: https://codeforces.com/contest/1423/submission/94770723
int mod = 1e9 + 7;

class Mint {
private:
  int value;

  template <typename T>
  static T inverse (T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
      T t = m / a;
      m -= t * a; swap(a, m);
      u -= t * v; swap(u, v);
    }
    assert(m == 1);
    return u;
  }

public:

  constexpr Mint (): value(0) {}

  template <class U>
  Mint (const U& x) { value = normalize(x); }

  template <class U>
  static int normalize (const U& x) {
    int ret;
    if (-mod <= x and x < mod) ret = x;
    else ret = x % mod;
    if (ret < 0) ret += mod;
    return ret;
  }

  static void set_mod (int new_mod) { mod = new_mod; }

  const int& operator ()() const { return value; }

  Mint& operator += (const Mint& other) { if ((value += other.value) >= mod) value -= mod; return *this; }
  Mint& operator -= (const Mint& other) { if ((value -= other.value) < 0) value += mod; return *this; }
  Mint& operator ++ () { return *this += 1; }
  Mint& operator -- () { return *this -= 1; }
  Mint operator ++ (int) { Mint ret(*this); *this += 1; return ret; }
  Mint operator -- (int) { Mint ret(*this); *this -= 1; return ret; }
  Mint operator - () const { return Mint(-value); }
  Mint& operator *= (const Mint& other) { value = normalize(1LL * value * other.value); return *this; }
  Mint& operator /= (const Mint& other) { return *this *= Mint(inverse(other.value, mod)); }

  friend bool operator == (const Mint& lhs, const Mint& rhs) { return lhs.value == rhs.value; }
  template <class U>
  friend bool operator == (const Mint& lhs, U rhs) { return lhs == Mint(rhs); }
  template <class U>
  friend bool operator == (U lhs, const Mint& rhs) { return Mint(lhs) == rhs; }

  friend bool operator != (const Mint& lhs, const Mint& rhs) { return not (lhs == rhs); }
  template <class U>
  friend bool operator != (const Mint& lhs, U rhs) { return not (lhs == rhs); }
  template <class U>
  friend bool operator != (U lhs, const Mint& rhs) { return not (lhs == rhs); }

  friend bool operator < (const Mint& lhs, const Mint& rhs) { return lhs.value < rhs.value; }

  friend Mint operator + (const Mint& lhs, const Mint& rhs) { return Mint(lhs) += rhs; }
  template <class U>
  friend Mint operator + (const Mint& lhs, U rhs) { return Mint(lhs) += rhs; }
  template <class U>
  friend Mint operator + (U lhs, const Mint& rhs) { return Mint(lhs) += rhs; }

  friend Mint operator - (const Mint& lhs, const Mint& rhs) { return Mint(lhs) -= rhs; }
  template <class U>
  friend Mint operator - (const Mint& lhs, U rhs) { return Mint(lhs) -= rhs; }
  template <class U>
  friend Mint operator - (U lhs, const Mint& rhs) { return Mint(lhs) -= rhs; }

  friend Mint operator * (const Mint& lhs, const Mint& rhs) { return Mint(lhs) *= rhs; }
  template <class U>
  friend Mint operator * (const Mint& lhs, U rhs) { return Mint(lhs) *= rhs; }
  template <class U>
  friend Mint operator * (U lhs, const Mint& rhs) { return Mint(lhs) *= rhs; }

  friend Mint operator / (const Mint& lhs, const Mint& rhs) { return Mint(lhs) /= rhs; }
  template <class U>
  friend Mint operator / (const Mint& lhs, U rhs) { return Mint(lhs) /= rhs; }
  template <class U>
  friend Mint operator / (U lhs, const Mint& rhs) { return Mint(lhs) /= rhs; }

  friend Mint power (Mint a, ll b) {
    assert(b >= 0);
    Mint ret = 1;
    while (b != 0) {
      if (b & 1) ret *= a;
      a *= a;
      b >>= 1;
    }
    return ret;
  }

  friend std::ostream& operator << (std::ostream& stream, const Mint& number) { return stream << number(); }

  friend std::istream& operator >> (std::istream& stream, Mint& number) {
    ll x;
    stream >> x;
    number.value = Mint::normalize(x);
    return stream;
  }

};

int check (int n) {
  vi perm(n);
  iota(all(perm), 0);
  int cnt = 0;
  do {
    vi vis(n, 0);
    bool ok = true;
    for (int pi: perm) {
      if (vis[pi]) ok = false;
      vis[pi] = 1;
      for (int i = 1; i + 1 < n; i++) {
        if (vis[i - 1] and vis[i + 1]) vis[i] = 1;
      }
    }
    cnt += ok;
  } while (next_permutation(all(perm)));
  return cnt;
};

// Modular Number Theory
struct MNT {
  vector <Mint> fact;
  vector <Mint> inv_fact;

  void preprocess_factorial (int n) {
    fact.resize(n + 1);
    inv_fact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
    ll z = 1;
    inv_fact[n] = 1 / fact[n];
    for (int i = n - 1; i >= 0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1);
  }

  Mint comb (int a, int b) {
    if (a < b) return 0;
    return fact[a] * inv_fact[b] * inv_fact[a - b];
  }
};

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  /*
  for (int z = 1; z <= 9; z++) cout << z << ' ' << check(z) << endl; 
  return 0;
  */
  int n, mod;
  cin >> n >> mod;
  Mint::set_mod(mod);
  MNT mnt;
  mnt.preprocess_factorial(n + 1);
  vector <Mint> z(n + 1);
  z[1] = 1;
  for (int i = 2; i <= n; i++) {
    z[i] = z[i - 1] * 2;
  }
  vector <vector <Mint>> dp(n, vector <Mint> (n + 1, 0));
  vector <vi> vis(n, vi(n + 1, 0));
  function <Mint(int,int)> rec = [&] (int pos, int total) -> Mint {
    if (pos == n) return 0;
    if (pos == n + 1) return mnt.fact[total];
    if (vis[pos][total]) return dp[pos][total];
    vis[pos][total] = 1;
    Mint ret = 0;
    for (int len = 1; pos + len - 1 <= n - 1; len++) {
      Mint add = z[len] * rec(pos + len + 1, total + len) / mnt.fact[len];
      ret += add;
    }
    return dp[pos][total] = ret;
  };
  cout << rec(0, 0) << '\n';
  return (0);
}

```