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;
typedef long long ll;
ll mod;
ll N;
ll Factorial[10000];
ll Inv[10000];
ll FactorialInv[10000];
ll dp[2005][2005];
ll beki2[5000000];
ll invbeki2[5000000];
ll beki(ll a, ll b) {
    a %= mod;
    if (a < 0) a += mod;
    if(b < 0) {
        ll inverse = beki(a, -b);
        return beki(inverse, mod - 2);
    }
    if(b == 0) return 1;
    ll ans = beki(a, b/2);
    ans = ans * ans % mod;
    if(b % 2 == 1) ans = ans * a % mod;
    return ans;
}

void init() {
    Inv[1] = 1;
    FactorialInv[1] = 1;
    Factorial[1] = 1;
    for(ll i = 2; i < 10000; i++) {
        Inv[i] = beki(i, mod - 2);
        Factorial[i] = Factorial[i-1] * i % mod;
        FactorialInv[i] = FactorialInv[i-1] * Inv[i] % mod;
    }
    beki2[0] = 1;
    invbeki2[0] = 1;
    for(int i = 1; i < 5000000; i++) {
        beki2[i] = beki2[i - 1] * 2 % mod;
        invbeki2[i] = invbeki2[i - 1] * Inv[2] % mod;
    }
    for(int y = 0; y <= 2000; y++) {
        ll Factor = (1 - invbeki2[y] + mod) % mod;
        dp[y][0] = 1;
        for(int z = 1; z <= 2000; z++) {
            dp[y][z] = dp[y][z-1] * Factor % mod;
        }
    }
}

ll combination(ll a, ll b) {
    if((a == b) || (b == 0)) return 1;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a-b] % mod;
    return ans;
}

int main() {
    cin >> N >> mod;
    //cerr << beki(2, -2) << endl;
    init();
    ll ans = 0;
    for(ll R = 0; R <= N; R++) {
        ll B = N - R;
        for(ll r = 0; r <= R; r++) {
           ll now = combination(R, r);
           now = now * beki2[N*(N-1)/2-r*B] % mod;
           //ll sub = 1 - invbeki2[R-r];
           //sub = (sub + mod) % mod;
           //sub = beki(sub, B);
           ll sub = dp[R-r][B];
           now = now * sub % mod;
           now = now * combination(N, R) % mod;
           if(r % 2 == 1) now = -now;
           //cout << R << " " << r << " " << now << endl;
           ans = (ans + now + mod) % mod;
        }
    }
    cout << ans << endl;
    return 0;
}
