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>
#define F first
#define S second
#define int long long
#define double long double
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,int> Pi;
typedef pair<P,P> PP;
double eps=1e-8;
int mod=1e9+7;
int inf=1LL<<55;

priority_queue<P,vector<P>,greater<P> > pq;


int mod_pow(int x,int n){
  int res=1;
  while(n){
    if(n%2) res=res*x%mod;
    x=x*x%mod;
    n/=2;
  }
  return res;
}

int divi(int a,int b){
  return a * mod_pow(b,mod-2) % mod;
}

int factorial(int i){
  static vector<int> k(1e6);
  if(!k[0]){k[0]=1;for(int i=1;i<(int)k.size();i++)k[i]=i*k[i-1]%mod;}
  return k[i];
}

int nCr(int n,int r){
  int a = mod_pow( factorial(r) * factorial(n-r) % mod ,mod-2);
  return factorial(n) * a % mod;
}


int cal(int a,int b){
  
  int res=mod_pow(mod_pow(2,b)-1,a),cnt=0,f=1;

  for(int i=b-1;i>=0;i--){
    int x=mod_pow(mod_pow(2,i)-1,a)*nCr(b,i)%mod;
    if(f)cnt=(cnt+x)%mod;
    else cnt=(cnt-x+mod)%mod;
    f=!f;
  }
  
  res=(res-cnt+mod)%mod;
  
  res=res*mod_pow(2,a*(a-1)/2)%mod*mod_pow(2,b*(b-1)/2)%mod;

  return res;
}

signed main(){
  int n,m;
  cin>>n>>m;
  mod=m;
  int ans=0;
  for(int i=1;i<n;i++){
    ans=(ans+nCr(n,i)*cal(i,n-i))%mod;
  }

  cout<<ans<<endl;

  return 0;
}

