#include<bits/stdc++.h> #pragma gcc optimize(2) #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define m_p make_pair #define pi pair<int,int> #define p1 first #define p2 second using namespace std; typedef long long ll; const int N=3010; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,mod,jc[N],jc_inv[N],pw[N][N],pw_inv[N][N],h[N][N],Al[N][N],dp[N],C[N][N],st[N][N],tp[N]; vector<int>v[N]; int gcd(int a,int b){return ((!b)?a:gcd(b,a%b));} int qpow(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } void init(){ jc[0]=jc_inv[0]=1;up(i,1,3000)jc[i]=jc[i-1]*1ll*i%mod,jc_inv[i]=qpow(jc[i],mod-2); up(i,1,3000){ pw[i][0]=pw_inv[i][0]=1; up(j,1,3000)pw[i][j]=pw[i][j-1]*1ll*i%mod; pw_inv[i][3000]=qpow(pw[i][3000],mod-2); down(j,2999,1)pw_inv[i][j]=pw_inv[i][j+1]*1ll*i%mod; } C[0][0]=1; up(i,1,3000){ up(j,0,i){ C[i][j]=C[i-1][j]; if(j)C[i][j]=(C[i][j]+C[i-1][j-1])%mod; } } } int f(int n,int x,int y){ //printf("f(%d,%d,%d)\n",n,x,y); int res=C[n][x*y]; //cout<<"test "<<res<<'\n'; res=res*1ll*pw_inv[y][x]%mod; res=res*1ll*jc[x*y]%mod; res=res*1ll*jc_inv[x]%mod; return res; } void slv(){ n=read(),mod=read();init(); up(k,1,n){ int p=gcd(k,n-1); st[k/p][++tp[k/p]]=p; } up(i,1,n){ Al[i][0]=1; up(j,1,tp[i]){ int x=st[i][j]; up(j,x,n/i)Al[i][j]|=Al[i][j-x]; } } dp[0]=1; up(i,1,n){ down(j,n,0){ up(k,1,j/i){ if(!Al[i][k])continue; (dp[j]+=dp[j-k*i]*1ll*f(n-(j-k*i),k,i)%mod)%=mod; } } } ll res=0; up(i,1,n)(res+=dp[i]*1ll*pw[i][n-i]%mod)%=mod; printf("%lld\n",res); }int main(){ // freopen("number.in","r",stdin); // freopen("number.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }