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;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class reverse_range {private:struct I {int x;int operator*() {return x-1;}bool operator!=(I& lhs) {return x>lhs.x;}void operator++() {--x;}};I i, n;public:reverse_range(int n) :i({ 0 }), n({ n }){}reverse_range(int i, int n) :i({ i }), n({ n }){}I& begin() {return n;}I& end() {return i;}};
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }reverse_range operator!(){return reverse_range(*i,*n);}};

int N;
int mod;

struct ModInt{
    int x;
    LL operator*()const{
        return x;
    }
    //constructor
    ModInt(){
        x=0;
    }
    ModInt(const int y){
        x=y;
    }
    ModInt(const LL y){
        x=(int)(y%mod);
    }
    static inline ModInt raw(const LL x){
        assert(x<mod);
        return ModInt((int)x);
    }
    static inline ModInt get(const LL x){
        return ModInt((int)(x%mod));
    }
    ModInt& operator=(const int o){
        this->x=o;
        return *this;
    }
    ModInt& operator=(const LL o){
        this->x=(int)(o%mod);
        return *this;
    }
};
inline ModInt mul(const ModInt l,const ModInt r){
    return ModInt::raw(*l**r%mod);
}
inline ModInt add(const ModInt l,const ModInt r){
    LL x = *l+*r;
    return ModInt::raw(x>=mod?x-mod:x);
}
inline ModInt inv(const ModInt x){
    LL a = *x, b = mod, u = 1, v = 0;
    while (b) {
        LL t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
    }
    return ModInt::raw((u % mod + mod) % mod);
}
inline ModInt operator-(const ModInt x){
    return add(mod, -*x);
}
inline ModInt operator+(const ModInt l,const ModInt r){
    return add(l,r);
}
inline ModInt operator*(const ModInt l,const ModInt r){
    return mul(l,r);
}
inline ModInt operator-(const ModInt l,const ModInt r){
    return add(l,-r);
}
inline ModInt operator+(const ModInt l,const int r){
    return add(l,ModInt::raw(r));
}
inline ModInt operator+(const ModInt l,const LL r){
    return add(l,ModInt::get(r));
}
inline ModInt operator*(const ModInt l,const int r){
    return mul(l,ModInt::raw(r));
}
inline ModInt operator*(const ModInt l,const LL r){
    return mul(l,ModInt::get(r));
}
inline ModInt operator-(const ModInt l,const int r){
    return add(l,ModInt::raw(mod-r));
}
inline ModInt operator-(const ModInt l,const LL r){
    return add(l,-ModInt::get(r));
}
inline ModInt operator/(const ModInt l,const int r){
    return mul(l,inv(ModInt::raw(r)));
}
inline ModInt operator/(const ModInt l,const LL r){
    return mul(l,inv(ModInt::get(r)));
}

inline ModInt pow(ModInt a, LL x){
    ModInt ret=1;
    while(x){
        if(x&1){
            ret=ret*a;
        }
        a=a*a;
        x>>=1;
    }
    return ret;
}

inline ModInt operator^(const ModInt l,const LL r){
    return pow(l,r);
}


namespace factorial{
    constexpr int size = 1123456;
    ModInt factorial[size];
    ModInt inverse_factorial[size];
    bool is_build = false;
    void build(){
        is_build = true;
        factorial[0]=1;
        for(int i:range(1,size)){
            factorial[i]=factorial[i-1]*i;
        }
        inverse_factorial[size-1]=inv(factorial[size-1]);
        for(int i:!range(1,size)){
            inverse_factorial[i-1]=inverse_factorial[i]*i;
        }
    }
    inline ModInt permutation(int n,int k){
        if(k<0 || k>n) return ModInt::raw(0);
        if(!is_build)build();
        return factorial[n]*inverse_factorial[n-k];
    }
    inline ModInt combination(int n, int k){
        if(k<0 || k>n) return ModInt::raw(0);
        if(!is_build)build();
        return factorial[n]*inverse_factorial[k]*inverse_factorial[n-k];
    }
}

ModInt bi[2123*2123];
ModInt ci[2123][2123];
ModInt calc(const int R){
    const int B=(N-R);
    vector<ModInt> Rs(2),Bs(2);
    for(int r:range(R)){
        Rs[r%2]=Rs[r%2]+factorial::combination(R,r)*ci[R-r][B];
    }
    return (Rs[0]-Rs[1])*bi[R*(R-1)/2+B*(B-1)/2];
}
int main(){
    cin>>N>>mod;
    bi[0]=1;
    for(int i:range(1,2123*2123)){
        bi[i]=bi[i-1]*2;
    }
    for(int r:range(1,2123)){
        ci[r][0]=1;
        for(int c:range(1,2123)){
            ci[r][c]=ci[r][c-1]*(bi[r]-1);
        }
    }
    ModInt ret=0;
    for(int i:range(1,N)){
        ret=ret+factorial::combination(N,i)*calc(i);
    }
    cout << *ret << endl;
    return 0;
}
