FFT 알고리즘

차수가 $2^k$ 미만인 다항식에 모듈러 연산 환경에서 FFT 알고리즘을 적용하려면, 원시 $2^k$차 단위근 $\omega$를 찾아야 한다.

두 정수 $m$과 $k$가 주어졌을 때, 다음 조건을 만족하는 정수 $\omega$를 찾아야 한다.

• $0 \le \omega < m$
• $\omega^{2^k} \equiv 1 \pmod{m}$
• $0 < p < 2^k$인 모든 $p$에 대해 $\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$을 출력한다.