Description

Find the smallest positive integer solution of $x$ to the congruence equation $a x \equiv 1 \pmod {b}$.

Input Format

One line containing two integers $a,b$, separated by a single space.

Output Format

A single integer $x_0$, which is the smallest positive solution. The input is guaranteed to have a solution.

3 10

7

Hint

Constraints

• For $40\%$ of the testdata, $2 \le b \le 1{,}000$.
• For $60\%$ of the testdata, $2 \le b \le 50{,}000{,}000$.
• For $100\%$ of the testdata, $2 \le a, b \le 2{,}000{,}000{,}000$.

Translated by ChatGPT 5