思路：
易知k = 0的时候答案是p，k = 1的时候答案是p。
当k >= 2的时候，f(0) = 0，对于 1 <= n <= p - 1，如果f(n)确定，由题意可知f(kn mod p)也随之确定，那么这种迭代什么时候停止呢？这就需要找出循环节，即能使k mod p = 1的最小的m，这个m就是k的阶数o(k)。这里(G = N- {0}, 模p乘法)实际上是一个循环群，设G中的元素k的阶数o(k) = m, 则k作为生成元生成的子群也是循环群，并且子群的阶为m且m能整除群的阶p-1。（参见离散数学（邓米克，邵学才等编著）清华大学出版社，p252）)，所以剩下的p-1(1 ~ p-1)个数实际上构成了(p - 1) / m 个同构的子循环群。这种情况下，答案就是
p。
实现：
import java.util.*;
public class Main {
private static final int mod = 1000000007;
public static long pow(long x, long n, long mod) {
long res = 1;
while (n > 0) {
if((n & 1) == 1)
res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long p = in.nextInt(), k = in.nextInt();
if (k == 0)
System.out.println(pow(p, p - 1, mod));
else if (k == 1)
System.out.println(pow(p, p, mod));
else {
long ord = 1;
long tmp = k;
while (tmp != 1) {
tmp = tmp * k % p % mod;
ord++;
}
System.out.println(pow(p, (p - 1) / ord, mod));
}
}
}