4995: Moodular Arithmetic
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2
通过：2
题目描述
B. Moodular Arithmetic
就像任何一个聪明的学生一样，凯文·孙(Kevin Sun)在波维尼亚州立大学(BGU)师从农民伊万(Farmer Ivan)，学习心理学、豇豆学和密码学。在他的奥数(MoO)课上，凯文遇到了一个奇怪的函数方程，需要你的帮助。对于两个固定整数k和p，其中p是一个奇素数，泛函方程表示
对于某个函数。(这个方程适用于0到p-1范围内的任何整数x。)
事实上f可以是很多不同的函数。凯文不想求解，而是想让你数出满足这个方程的不同函数f的个数。因为答案可能很大，你应该对109+7取模输出结果。
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
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.
Input
The input consists of two space-separated integers p and k (3≤p≤1000000, 0≤k≤p-1) on a single line. It is guaranteed that p is an odd prime number.
Output
Print a single integer, the number of distinct functions f modulo 109+7.
Examples
Input
3 2
Output
3
Input
5 4
Output
25
Note
In the first sample, p=3 and k=2. The following functions work: - f(0)=0, f(1)=1, f(2)=2.
- f(0)=0, f(1)=2, f(2)=1.
- f(0)=f(1)=f(2)=0.
输入样例 复制
输出样例 复制