ll@N,@B,C[B]{},i;modint t;t.setmod(B);rep(x,B)C[i=(t=x).pw(N)]++;wt(sum[(n,m),0,B](C[n]*C[m]*C[(n+m)%B]));