D. FFT Algorithm
time limit per test
1.5 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

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 \lt m$$$,
  • $$$\omega^{2^{k}} \equiv 1 \pmod m$$$,
  • $$$\omega^{p} \not\equiv 1 \pmod m$$$ for all $$$0 \lt p \lt 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).

Input

The only line of input contains two integers $$$m$$$ and $$$k$$$ ($$$2 \le m \le 4 \cdot 10^{18}$$$, $$$15 \le k \le 23$$$).

Output

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

Examples
Input
998244353 23
Output
422962976
Input
1048576 15
Output
95905
Input
3 23
Output
-1