Số học bò (Moodular Arithmetic)

Cho hai số nguyên $k$ và $p$, trong đó $p$ là một số nguyên tố lẻ. Hãy đếm số hàm $f:\{0,1,\dots ,p-1\}\to \{0,1,\dots ,p-1\}$ thoả mãn:

$$f(kxmodp)\equiv k·f(x)\left(\mathrm{mod}p\right)$$

với mọi $x\in \{0,1,\dots ,p-1\}$.

Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $p$ và $k$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất — số hàm $f$ phân biệt thoả mãn điều kiện trên, lấy theo modulo ${10}^9+7$.

Ràng buộc

• $3\le p\le {10}^6$
• $0\le k\le p-1$
• $p$ là số nguyên tố lẻ.

Ví dụ