版权声明

本题版权归 Long Long OJ 所有。

题目描述

给定整数 $p,k$，问有多少种方案构造出一个长度为 $p$ 的非负整数序列 $f$（下标从 $0$ 开始），满足对于任意 $0$ 到 $p-1$ 之间的整数 $x$，$f_{kx\bmod p}=kf_x\bmod p$。

答案对 $10^9+7$ 取模。

输入格式

一行两个整数，分别表示 $p$ 和 $k$。

输出格式

一行一个整数，表示方案数。

样例

3 2

3

5 4

25

提示

样例 $1$ 解释：

$3$ 种合法的序列如下：

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$。

对于 $10\%$ 的数据，$3\le p \le 7$。

对于另外 $10\%$ 的数据，$k=0$。

对于另外 $10\%$ 的数据，$k=1$。

对于 $100\%$ 的数据，$3\le p \le 10^6$，$0 \le k \le p-1$，且 $p$ 为质数。