Số học mô-đun

Cho hai số nguyên cố định $k$ và $p$, trong đó $p$ là một số nguyên tố lẻ. Xét phương trình hàm sau đối với hàm số $f:\{0,1,\dots ,p-1\}\to \{0,1,\dots ,p-1\}$:

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

Phương trình trên phải đúng với mọi số nguyên $x$ trong khoảng từ $0$ đến $p-1$.

Hãy đếm số hàm $f$ phân biệt thỏa mãn phương trình trên. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó 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 thỏa mãn phương trình, lấy phần dư cho ${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ụ