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

struct dynamic_mint {
	static int M;
	static void set_mod(int m) { assert(0 < m); M = m; }

	int val;
	dynamic_mint(): val() {}
	dynamic_mint(long long x) : val(x % M) { if (val < 0) { val += M; } }
	dynamic_mint pow(long long n) const { dynamic_mint ans = 1, x(*this); while (n) { if (n & 1) ans *= x; x *= x; n /= 2; } return ans; }
	dynamic_mint inv() const { return pow(M - 2); }

	friend dynamic_mint pow(const dynamic_mint &m, long long n) { return m.pow(n); }
	friend dynamic_mint inv(const dynamic_mint &m) { return m.inv(); }

	dynamic_mint operator+() const { dynamic_mint m; m.val = val; return m; }
	dynamic_mint operator-() const { dynamic_mint m; m.val = M - val; return m; }
	dynamic_mint &operator+=(const dynamic_mint &m) { if ((val += m.val) >= M) val -= M; return *this; }
	dynamic_mint &operator-=(const dynamic_mint &m) { if ((val -= m.val) < 0) val += M; return *this; }
	dynamic_mint &operator*=(const dynamic_mint &m) { val = (long long) val * m.val % M; return *this; }
	dynamic_mint &operator/=(const dynamic_mint &m) { val = (long long) val * m.inv().val % M; return *this; }

	friend dynamic_mint operator+ (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) += rhs; }
	friend dynamic_mint operator- (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) -= rhs; }
	friend dynamic_mint operator* (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) *= rhs; }
	friend dynamic_mint operator/ (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) /= rhs; }
	friend bool operator==(const dynamic_mint &lhs, const dynamic_mint &rhs) { return lhs.val == rhs.val; }
	friend bool operator!=(const dynamic_mint &lhs, const dynamic_mint &rhs) { return lhs.val != rhs.val; }

	dynamic_mint &operator++() { return *this += 1; }
	dynamic_mint &operator--() { return *this -= 1; }
	dynamic_mint operator++(int) { dynamic_mint result(*this); *this += 1; return result; }
	dynamic_mint operator--(int) { dynamic_mint result(*this); *this -= 1; return result; }

	template <typename T> explicit operator T() const { return T(val); }

	friend std::ostream &operator<<(std::ostream &os, const dynamic_mint &m) {
		return os << m.val;
	}

	friend std::istream &operator>>(std::istream &is, dynamic_mint &m) {
		long long x; is >> x; m = x;
		return is;
	}
};

int dynamic_mint::M;

template <typename>
struct is_mint : public std::false_type { };

template <>
struct is_mint<dynamic_mint> : public std::true_type { };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	using mint = dynamic_mint;

	int n, M;
	cin >> n >> M;

	mint::set_mod(M);

	vector<mint> fact(n + 1); fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = i * fact[i - 1];
	}

	vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
	dp[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] += j * dp[i - 1][j] + dp[i - 1][j - 1];
		}
	}

	mint ans = mint(2).pow(n - 1);
	for (int holes = 1; n - 2 * holes - 1 >= 0; holes++) {
		ans += mint(2).pow(n - 2 * holes - 1) * fact[holes + 1] * dp[n - holes][holes + 1];
	}
	cout << ans << '\n';
	return 0;
}
### Prompt

Generate 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;

struct dynamic_mint {
	static int M;
	static void set_mod(int m) { assert(0 < m); M = m; }

	int val;
	dynamic_mint(): val() {}
	dynamic_mint(long long x) : val(x % M) { if (val < 0) { val += M; } }
	dynamic_mint pow(long long n) const { dynamic_mint ans = 1, x(*this); while (n) { if (n & 1) ans *= x; x *= x; n /= 2; } return ans; }
	dynamic_mint inv() const { return pow(M - 2); }

	friend dynamic_mint pow(const dynamic_mint &m, long long n) { return m.pow(n); }
	friend dynamic_mint inv(const dynamic_mint &m) { return m.inv(); }

	dynamic_mint operator+() const { dynamic_mint m; m.val = val; return m; }
	dynamic_mint operator-() const { dynamic_mint m; m.val = M - val; return m; }
	dynamic_mint &operator+=(const dynamic_mint &m) { if ((val += m.val) >= M) val -= M; return *this; }
	dynamic_mint &operator-=(const dynamic_mint &m) { if ((val -= m.val) < 0) val += M; return *this; }
	dynamic_mint &operator*=(const dynamic_mint &m) { val = (long long) val * m.val % M; return *this; }
	dynamic_mint &operator/=(const dynamic_mint &m) { val = (long long) val * m.inv().val % M; return *this; }

	friend dynamic_mint operator+ (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) += rhs; }
	friend dynamic_mint operator- (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) -= rhs; }
	friend dynamic_mint operator* (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) *= rhs; }
	friend dynamic_mint operator/ (const dynamic_mint &lhs, const dynamic_mint &rhs) { return dynamic_mint(lhs) /= rhs; }
	friend bool operator==(const dynamic_mint &lhs, const dynamic_mint &rhs) { return lhs.val == rhs.val; }
	friend bool operator!=(const dynamic_mint &lhs, const dynamic_mint &rhs) { return lhs.val != rhs.val; }

	dynamic_mint &operator++() { return *this += 1; }
	dynamic_mint &operator--() { return *this -= 1; }
	dynamic_mint operator++(int) { dynamic_mint result(*this); *this += 1; return result; }
	dynamic_mint operator--(int) { dynamic_mint result(*this); *this -= 1; return result; }

	template <typename T> explicit operator T() const { return T(val); }

	friend std::ostream &operator<<(std::ostream &os, const dynamic_mint &m) {
		return os << m.val;
	}

	friend std::istream &operator>>(std::istream &is, dynamic_mint &m) {
		long long x; is >> x; m = x;
		return is;
	}
};

int dynamic_mint::M;

template <typename>
struct is_mint : public std::false_type { };

template <>
struct is_mint<dynamic_mint> : public std::true_type { };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	using mint = dynamic_mint;

	int n, M;
	cin >> n >> M;

	mint::set_mod(M);

	vector<mint> fact(n + 1); fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = i * fact[i - 1];
	}

	vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
	dp[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] += j * dp[i - 1][j] + dp[i - 1][j - 1];
		}
	}

	mint ans = mint(2).pow(n - 1);
	for (int holes = 1; n - 2 * holes - 1 >= 0; holes++) {
		ans += mint(2).pow(n - 2 * holes - 1) * fact[holes + 1] * dp[n - holes][holes + 1];
	}
	cout << ans << '\n';
	return 0;
}
```