#include<iostream> using namespace std; int M,K; const long mod=1e9+7; long E[50][50],A[50][50],T[50][50]; main() { cin>>M>>K; for(int i=0;i<M;i++) { for(int j=0;j<M;j++) { A[(i+j)%M][i]++; A[i*j%M][i]++; } E[i][i]=1; } while(K) { if(K&1) { for(int i=0;i<M;i++)for(int j=0;j<M;j++)T[i][j]=E[i][j],E[i][j]=0; for(int i=0;i<M;i++)for(int j=0;j<M;j++) { for(int k=0;k<M;k++)(E[i][j]+=T[i][k]*A[k][j])%=mod; } } K>>=1; for(int i=0;i<M;i++)for(int j=0;j<M;j++)T[i][j]=A[i][j],A[i][j]=0; for(int i=0;i<M;i++)for(int j=0;j<M;j++) { for(int k=0;k<M;k++)(A[i][j]+=T[i][k]*T[k][j])%=mod; } } cout<<E[0][0]<<endl; }