← 返回题目列表

Codeforces · 603/B

B. 模数运算

中文机器翻译题面 查看原题

作为一个聪明的学生,凯文·孙 (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。