当我想在模运算中对次数小于 $2^k$ 的多项式应用 FFT 算法时，我需要找到 $\omega$ —— 一个 $2^k$ 次本原单位根。

形式化地，对于给定的两个整数 $m$ 和 $k$，我需要找到任意一个整数 $\omega$ 满足：

• $0 \le \omega < m$
• $\omega^{2^k} \equiv 1 \pmod m$
• 对于所有 $0 < p < 2^k$，都有 $\omega^p \not\equiv 1 \pmod m$

在本题中，请你帮我找到这个 $\omega$，或者确定它不存在。由于我们讨论的是 FFT 的应用，我为 $k$ 设置了一些合理的限制：对于较小的 $k$，朴素的多项式乘法已经足够，而对于较大的 $k$，FFT 的耗时会超过 1 秒（毕竟我们是竞赛选手）。

输入格式

输入仅一行，包含两个整数 $m$ 和 $k$ ($2 \le m \le 4 \cdot 10^{18}$, $15 \le k \le 23$)。

输出格式

输出任意一个满足条件的 $\omega$，如果不存在这样的 $\omega$，则输出 $-1$。

样例

样例输入 1

998244353 23

样例输出 1

683321333

样例输入 2

1048576 15

样例输出 2

64609

样例输入 3

3 23

样例输出 3

-1