#include <bits/stdc++.h> using namespace std; #define int long long #pragma GCC optimize(2) int C[3010][3010]; int fac[3010]; int n,M; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } inline int inv(int x){return qp(x,M-2);} inline int gcd(int a,int b){ return b?gcd(b,a%b):a; } inline void add(int &x,int y){ x+=y; if(x>=M)x-=M; } int f[3010]; vector<int>T[3010]; bool alow[3010][3010]; int pw[3010][3010]; int ivpw[3010][3010]; int ivfac[3010]; int G[3010][3010]; inline int g(int n,int p,int k){ return C[n][p*k]*G[p][k]%M; } signed main(){ //freopen("number.in","r",stdin); //freopen("number.out","w",stdout); cin>>n>>M; fac[0]=1; C[0][0]=1; ivfac[0]=1; for(int i=1;i<=n;i++){ fac[i]=fac[i-1]*i%M; ivfac[i]=inv(fac[i]); C[i][0]=1; for(int j=1;j<=n;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%M; } f[0]=1; for(int i=0;i<=n;i++){ ivpw[i][0]=1,ivpw[i][1]=inv(i); for(int j=2;j<=n;j++) ivpw[i][j]=ivpw[i][j-1]*ivpw[i][1]%M; } for(int i=1;i<=n;i++) for(int j=1;j*i<=n;j++) G[i][j]=fac[i*j]*ivpw[j][i]%M*ivfac[i]%M; for(int k=1;k<=n;k++) T[k/gcd(n-1,k)].emplace_back(gcd(n-1,k)); for(int i=1;i<=n;i++){ alow[i][0]=1; for(int x:T[i]){ for(int p=x;p*i<=n;p++) alow[i][p]|=alow[i][p-x]; } } int cnt=0; for(int k=1;k<=n;k++){ for(int i=n;i>=1;i--) for(int j=1;j*k<=i;j++){ if(alow[k][j])add(f[i],f[i-j*k]*g(n-i+j*k,j,k)%M);} } int res=0; for(int i=1;i<=n;i++) add(res,f[i]*qp(i,n-i)%M); cout<<res<<endl; cout.flush(); return 0; }