Modular Inverse

Difficulty: 1500 2000 ms 128 MB

math

Print the modular inverse of A modulo the prime 10⁹+7 — the unique X in [1, 10⁹+6] with A·X ≡ 1.

Input: one integer A.

Output: the inverse of A mod 10⁹+7.

Constraints:

• 1 ≤ A ≤ 10⁹+6

Sample Tests

2

500000004

1

1

Read the Editorial