18491번 - FFT Algorithm 스페셜 저지다국어

When I want to apply FFT algorithm to polynomial of degree less than 2^k in modular arithmetics, I have to find ω — a primitive 2^k-th root of unity.

Formally, for two given integers m and k, I should find any integer ω such that:

• 0 ≤ ω < m,
• ω^2k ≡ 1 (mod m),
• ω^p ≠ 1 (mod m) for all 0 < p < 2^k.

In this task, I ask you to find ω for me, or determine that it does not exist. Since we talk about application of FFT, I’ve set some reasonable limitations for k: for smaller k naive polynomial multiplication is fine, and for larger k FFT takes more than 1 second (we are competitive programmers after all).

The only line of input contains two integers m and k (2 ≤ m ≤ 4 · 10¹⁸, 15 ≤ k ≤ 23).

Print any ω satisfying the criteria, or print −1 if there is no such ω.