ll m,k;{rd(m,k);Matrix<Mint>a(m,m);rep(i,m)rep(j,m)(a[i][j],a[i][i*j%m])+=1;wt(*(a**k)[0]);}