Modular Inverse

Return the number x with 0 <= x < m such that (a * x) % m == 1, the modular inverse of a modulo m. If there is no such x, return -1. For m = 1 the answer is 0.

For a = 3 and m = 11 the answer is 4 (3 × 4 = 12 = 1 mod 11); for a = 2 and m = 4 it is -1.

Examples

Example 1

Input:

mod_inverse(3, 11)

Output:

4

Example 2

Input:

mod_inverse(2, 4)

Output:

-1

Constraints

• 1 <= m <= 10**9 + 7
• 0 <= a <= 10**18