CF603B.Moodular Arithmetic

As behooves any intelligent schoolboy, Kevin Sun is studying psycowlogy, cowculus, and cryptcowgraphy at the Bovinia State University (BGU) under Farmer Ivan. During his Mathematics of Olympiads (MoO) class, Kevin was confronted with a weird functional equation and needs your help. For two fixed integers k and p, where p is an odd prime number, the functional equation states that

for some function . (This equation should hold for any integer x in the range 0 to p - 1, inclusive.)

It turns out that f can actually be many different functions. Instead of finding a solution, Kevin wants you to count the number of distinct functions f that satisfy this equation. Since the answer may be very large, you should print your result modulo 109 + 7.

正如任何一位聪明的中学生所应做的那样，凯文·孙（Kevin Sun）正在波维尼亚州立大学（Bovinia State University，BGU）跟随伊万农夫（Farmer Ivan）学习“牛理学”（psycowlogy）、“牛微积分”（cowculus）和“密码牛学”（cryptcowgraphy）。在“奥林匹克数学”（Mathematics of Olympiads，MoO）课上，凯文遇到了一个奇怪的函数方程，需要你的帮助。给定两个固定整数 $k$ 和 $p$，其中 $p$ 是一个奇素数，该函数方程表述为：

对某个函数 成立。（该等式应对任意整数 $x$（满足 $0 \le x \le p-1$）均成立。）

事实上，满足该方程的函数 $f$ 可能有多种不同形式。凯文并不要求你具体找出某个解，而是希望你计算出满足该方程的互不相同的函数 $f$ 的个数。由于答案可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

The input consists of two space-separated integers p and k (3 ≤ p ≤ 1 000 000, 0 ≤ k ≤ p - 1) on a single line. It is guaranteed that p is an odd prime number.

输入包含一行，其中有两个用空格分隔的整数 $p$ 和 $k$（$3 \leq p \leq 1\,000\,000$，$0 \leq k \leq p - 1$）。保证 $p$ 是一个奇素数。

Print a single integer, the number of distinct functions f modulo 109 + 7.

输出一个整数，表示模 $10^9 + 7$ 意义下不同的函数 $f$ 的个数。

In the first sample, p = 3 and k = 2. The following functions work:

1. f(0) = 0, f(1) = 1, f(2) = 2.
2. f(0) = 0, f(1) = 2, f(2) = 1.
3. f(0) = f(1) = f(2) = 0.

在第一个样例中，$p = 3$ 且 $k = 2$。以下函数满足要求：

1. $f(0) = 0$，$f(1) = 1$，$f(2) = 2$。
2. $f(0) = 0$，$f(1) = 2$，$f(2) = 1$。
3. $f(0) = f(1) = f(2) = 0$。