#D0130. 同余方程 (Congruence Equation)

同余方程 (Congruence Equation)

Description

Find the smallest positive integer xx such it satisfies the congruence equation ax1(modb)ax \equiv 1 \pmod{b}.

Input Format

The input is only one line, containing two positive integers a,ba, b separated by a space.

Output Format

The output is only one line and contains a positive integer x0x_0, that is, the smallest positive integer solution. The input data is guaranteed to have a solution.

3 10
7

Constraints

For 40%40\% data, 2b1032 \leq b \leq 10^3.
For 60%60\% data, 2b5×1072 \leq b \leq 5 \times 10^7.
For 100%100\% data, 2a,b2×1092 \leq a, b\leq 2 \times 10^9.