問題文

非負整数 N, M が与えられます。

10^{18} 以下の正整数 x であって x^x \equiv N \pmod M を満たすものが存在するか判定し、存在する場合はそのような x を 1 つ求めてください。

制約

• 0 \leq N < M \leq 10^9
• 入力される値はすべて整数

部分点

以下の制約を満たすデータセットに正解した場合には 1 点が与えられる。

• M が素数

入力例 1

3 7

出力例 1

5

5^5 = 3125 \equiv 3 \pmod 7 です。

入力例 2

2 6

出力例 2

-1

x^x \equiv 2 \pmod 6 なる 10^{18} 以下の正整数 x は存在しません。