AT_kupc2024_f Find x

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

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $

$ 10^{18} $ 以下の正整数 $ x $ であって $ x^x \equiv N \pmod M $ を満たすものが存在する場合、そのような $ x $ の値を $ 1 $ つ出力せよ。そのような $ x $ が存在しないとき、 $ -1 $ を出力せよ。

### 部分点 以下の制約を満たすデータセットに正解した場合には $ 1 $ 点が与えられる。 - $ M $ が素数 ### Sample Explanation 1 $ 5^5 = 3125 \equiv 3 \pmod 7 $ です。 ### Sample Explanation 2 $ x^x \equiv 2 \pmod 6 $ なる $ 10^{18} $ 以下の正整数 $ x $ は存在しません。 ### Constraints - $ 0 \leq N < M \leq 10^9 $ - 入力される値はすべて整数