Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

Given integers $p$ and $k$, find the number of ways to construct a non-negative integer sequence $f$ of length $p$ (indexed from $0$) such that for any integer $x$ between $0$ and $p-1$, $f_{kx\bmod p}=kf_x\bmod p$.

The answer should be taken modulo $10^9+7$.

Input Format

A single line containing two integers, representing $p$ and $k$ respectively.

Output Format

A single line containing an integer, representing the number of valid schemes.

Samples

3 2

3

5 4

25

Sample 1 Explanation

The 3 valid sequences are as follows:

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

Data Range

• For $10\%$ of the data: $3\le p \le 7$.
• For another $10\%$ of the data: $k=0$.
• For another $10\%$ of the data: $k=1$.
• For $100\%$ of the data: $3\le p \le 10^6$, $0 \le k \le p-1$, and $p$ is a prime number.