// same as https://yukicoder.me/submissions/875319 #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #define rd() ({long _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;}) #define wt(v) ({ulong _z=v;do*--wp=_z%10+48;while(_z/=10);}) #define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);}) #define rep3(v,s,e) for(typeof(e) v=s;v>=1; a=a*a%MD; } return r; } int main(){ ulong n,p; { char rbuf[64]; read(0,rbuf,sizeof rbuf); char*rp=rbuf; n=rd(); p=rd(); } ulong a=1,b=1,c=0; rep3(i,1,n+1){ a=a*i%(MD-1); b=b*i%MD; } while(n){ c+=n/=p; } b=modpow(b,a)*c%MD; wt1(b); _exit(0); }