integer(16)::i,j,m,k,a(0:49,0:49),t(0:49,0:49),d=1d9+7
read*,m,k
do i=0,m-1
a(i,i)=1
do j=0,m-1
t(mod(i+j,m),i)=t(mod(i+j,m),i)+1
t(mod(i*j,m),i)=t(mod(i*j,m),i)+1
enddo
enddo
do while(k>0)
if(mod(k,2)==1)a=mod(matmul(a,t),d)
t=mod(matmul(t,t),d)
k=k/2
enddo
print*,a(0,0)
end