406966: GYM102638 B WA6

Becoming blue on Codeforces is something to be proud of, especially at the age of ten.

The fifth grader Vasya has recently become blue on CF, and to celebrate it he decided to implement a new advanced algorithm that he learnt from cp-algorithms. The algorithm is called "Modular Multiplicative Inverse". This algorithm finds the modular multiplicative inverse given a number and a module.

Vasya decided to use it to solve a problem on a famous platform for young programmers — Codeforces. The problem goes as follows: given two integers $$$n$$$ and $$$M$$$ ($$$1 \le n < M \le 10^9 +7$$$), find such a number $$$k$$$ that $$$n \cdot k \equiv 1 (\mod M)$$$; $$$1 \le k < M$$$; $$$M$$$ is a prime.

Thanks to the article mentioned above, Vasya knows that it is enough to raise $$$n$$$ to the power of $$$M - 2$$$ modulo $$$M$$$ to obtain the answer, and, of course, he didn't bother to prove this. Vasya quickly implemented the code for that problem. However, he became discouraged as soon as his wonderful solution got WA6. Feeling deeply offended, he deleted his code and decided to rage quit competitive programming. Nevertheless, on the next day he didn't get any homework and decided to recover his code and find the bugs.

Help Vasya recover his incorrect solution!

Two integer numbers, separated by space: $$$n$$$ and $$$M$$$, $$$1 \le n < M \le 10^9+7$$$.

Print one integer $$$k$$$ — the output of Vasya's program for the given test.

1 5

1

2 7

4

3 23

8