A cipher wheel needs the multiplicative inverse of a modulo m: the value x in 0..m-1 such that (a * x) mod m = 1 mod m. The inverse exists exactly when gcd(a, m) = 1, and it is unique in that range. If no inverse exists, report -1. Note that when m = 1, every product is congruent to 0, which equals 1 mod 1, so the inverse is defined to be 0.
Input format
A single line with two integers a and m.
Output format
A single integer: the modular inverse of a modulo m in 0..m-1, or -1 if it does not exist.
Constraints
- 0 <= a <= 1000000000
- 1 <= m <= 1000000