Modular Inverse

Statement

Given integers a and m, find an integer x with 0 <= x < m such that (a * x) mod m equals 1 mod m. If no such x exists, print -1. (When m is 1, every number is congruent to 0, and x = 0 is the answer.)

Input

One line with a and m.

Output

Print x, or -1 if there is no inverse.

Constraints

1 <= a <= 10^9
1 <= m <= 10^9
m is not necessarily prime.

Example 1

3 11

4

3 * 4 = 12, and 12 mod 11 = 1.

Example 2

4 8

-1

4 and 8 share a factor, so 4 has no inverse modulo 8.