Modular Inverse

Interview

Time limit2sMemory limit1024 MB

Summary

Given a prime m and a number a with 1 at most a less than m, find b in [1, m) with a times b leaving remainder 1 modulo m.

Level: Easy3 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

The day before yesterday, Roma learned a new math operation: taking the remainder modulo $m$ , written $a \operatorname{mod} m$ . For example, $5 \operatorname{mod} 3 = 2$ . Here $a \operatorname{mod} m = b$ means $a = m \cdot k + b$ with $0 \le b < m$ , where all numbers are integers.

Yesterday Roma started multiplying numbers and noticed that sometimes $(a \cdot b) \operatorname{mod} m = 1$ , even when neither number is 1. He found this interesting and named it: $a$ and $b$ are called mutual inverses modulo $m$ .

This morning Roma looked at prime numbers $m$ . He proved that for every $a$ with $1 \le a < m$ , there is exactly one $b$ such that $(a \cdot b) \operatorname{mod} m = 1$ . However, he does not know how to find $b$ from $a$ and $m$ . Help him!

Input

A single line contains the numbers $a$ and $m$ ( $1 \le a < m \le 2 \cdot 10^9$ ). The number $m$ is prime.

Output

Print the number $b$ such that $(a \cdot b) \operatorname{mod} m = 1$ . It must also satisfy $1 \le b < m$ .

Examples2

Example 1
Input
```
3 7
```
Expected output
```
5
```
Example 2
Input
```
6 23
```
Expected output
```
4
```