시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 4 2 2 50.000%

문제

When I want to apply FFT algorithm to polynomial of degree less than 2k in modular arithmetics, I have to find ω — a primitive 2k-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 < 2k.

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 · 1018, 15 ≤ k ≤ 23).

출력

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

예제 입력 1

998244353 23

예제 출력 1

683321333

예제 입력 2

1048576 15

예제 출력 2

64609

예제 입력 3

3 23

예제 출력 3

-1