ll M,K;{rd(M,K);Matrix<mint>A(M,M);rep(i,M)rep(j,M)A[i][(i+j)%M]+=1,A[i][i*j%M]+=1;wt(*(A**K)[0]);}