408677: GYM103261 D FFT Algorithm

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

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

• $$$0 \le \omega < m$$$,
• $$$\omega^{2^{k}} \equiv 1 \pmod m$$$,
• $$$\omega^{p} \not\equiv 1 \pmod m$$$ for all $$$0 < p < 2^{k}$$$.

In this task, I ask you to find $$$\omega$$$ 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 \le m \le 4 \cdot 10^{18}$$$, $$$15 \le k \le 23$$$).

Print any $$$\omega$$$ satisfying the criteria, or print $$$-1$$$ if there is no such $$$\omega$$$.

998244353 23

422962976

1048576 15

95905

3 23

-1