AT_joisc2007_fermat.フェルマー方程式 (Fermat)

给定素数 $p$ 和自然数 $n$，请求出满足下面这个方程的 $(x,y,z)$ 的组数：

$$x^n+y^n\equiv z^n(\bmod\ p)$$

其中，$0\le x,y,z\le n-1$。

两行两个整数 $p,n$。

一行一个整数，解的组数。

保证答案 $\lt 2^{31}$。

输入输出样例

输入 #1

3
5

输出 #1

9

输入 #2

19
21

输出 #2

487

数据规模与约定

对于全部测试点，保证 $p\lt 10000$，$1\le n\le 10000$。