F: Red-Black Soul Gem

problem

Homu-chan has the mysterious power to change the soul game to red or black, and to connect two different soul games with a magic thread. By using this power, Homu-chan can create a magic square by Sorujemu.

Homu-chan was wondering how many different magic squares there were when there were N numbered magic squares numbered from 1 to N, and the following conditions were met:

* You can only connect once between any of the two sources.
* All the colors of the game are either red or black.
* For any game, it is connected to at least one of the games whose color is different from its own.



At this time, the magic square can be regarded as a graph with the sorujemu as the apex and the magic thread as the side. Note that the graph does not have to be concatenated.

Homu-chan is not good at calculating, so let's create a fast program instead and calculate the number of different magic squares. However, the number is expected to be very large, so we will find the remainder after dividing by a prime number M.

Note that the magic squares G and H are different because the colors of G and H are different for a certain magic square v, or the pair u and v of a certain magic square is one of G and H. It means that it is connected only with.

Input format


N M

Constraint

* 2 \ leq N \ leq 2,000
* 10 ^ 8 \ leq M \ leq 10 ^ 9 + 7
* M is guaranteed to be prime



Output format

Divide the number of graphs that satisfy the condition by M and output the remainder as an integer on one line.

Input example 1


3 310779401

Output example 1


12

For example, the following magic squares meet the conditions.

Input example 2


7 566666561

Output example 2


98638848

For example, the following magic squares meet the conditions.

Input example 3


1010 1000000007

Output example 3


862232855

Note that we output the remainder after dividing by M.





Example

Input

3 310779401


Output

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

::std::pair<::std::int64_t, ::std::int64_t> extgcd(::std::int64_t a, ::std::int64_t b) {
	::std::pair<::std::int64_t, ::std::int64_t> pa(1, 0), pb(0, 1);
	while (b != 0) {
		::std::swap(a, b); ::std::swap(pa, pb);
		pb = ::std::make_pair(pb.first - pa.first * (b / a), pb.second - pa.second * (b / a));
		b = b % a;
	}
	return pa;
}

::std::int64_t modinv(::std::int64_t a, ::std::int64_t mod) {
	::std::int64_t x = extgcd(a, mod).first;
	if (x < 0) x += mod;
	return x;
}

::std::int64_t modpow(::std::int64_t a, ::std::int64_t b, ::std::int64_t mod) {
	::std::int64_t res = 1;
	while (b > 0) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int64 N, mod;
vector<int64> fact, inv;

void init() {
	fact.resize(11234, 1); inv.resize(11234, 1);
	REP(i, 11234) {
		fact[i+1] = fact[i] * (i+1) % mod;
		inv[i+1] = modinv(fact[i+1], mod);
	}
}

int64 comb(int64 a, int64 b) {
	return fact[a] * inv[b] % mod * inv[a-b] % mod;
}

int main(void) {
	cin >> N >> mod;
	init();
	int64 res = 0;
	FOR(i, 1, N) {
		int64 ret = comb(N, i);
		ret = ret * modpow(2, i*(i-1)/2, mod) % mod;
		ret = ret * modpow(2, (N-i)*(N-i-1)/2, mod) % mod;
		int64 sum = 0;
		REP(j, i+1) {
			sum += (j%2 ? -1 : 1) * comb(i, j) * modpow(modpow(2, i-j, mod)-1, N-i, mod) % mod;
			sum %= mod;
			if (sum < 0) sum += mod;
		}
		res += ret * sum % mod;
		res %= mod;
	}
	cout << res << endl;
}


