作为一个聪明的学生,凯文·孙 (Kevin Sun) 正在玻维尼亚州立大学 (BGU) 师从法默·伊万 (Farmer Ivan) 学习心理学、牛科勒斯和密码学。在奥林匹克数学 (MoO) 课上,凯文遇到了一个奇怪的函数方程,需要你的帮助。对于两个固定整数 k 和 p,其中 p 是奇素数,函数方程表明
$$f(kx \mod p) \equiv k \cdot f(x) \mod p$$
对于某些函数 $$f:\{0, 1, 2, \cdots, p-1\} \到 \{0, 1, 2, \cdots, p-1\}$$。 (这个方程对于 0 到 p - 1 范围内的任何整数 x 都成立。)
事实证明,f 实际上可以是许多不同的函数。 Kevin 希望您计算满足该方程的不同函数 f 的数量,而不是寻找解决方案。由于答案可能非常大,因此您应该打印对 109 + 7 取模的结果。
输入
输入由单行上的两个空格分隔的整数 p 和 k (3 ≤ p ≤ 1 000 000, 0 ≤ k ≤ p - 1) 组成。保证p是奇素数。
输出
打印单个整数,不同函数的数量 f 模 109 + 7。
示例
输入 #1
3 2
输出 #1
3
输入 #2
5 4
输出 #2
25
注意
在第一个示例中,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。