题目描述

求关于 $x$ 的同余方程 $ax \equiv 1 \pmod{b}$ 的最小正整数解。

输入格式

输入只有一行，包含两个正整数 $a,b$，用一个空格隔开。

输出格式

输出只有一行，包含一个正整数 $x$，表示最小正整数解。

输入数据保证一定有解。

样例

输入样例：

3 10

输出样例：

7

样例解释

方程 $3x \equiv 1 \pmod{10}$
验证：$3 \times 7 = 21$，$21 \bmod 10 = 1$，所以 $x=7$ 是解。
并且 $7$ 是最小的正整数解。

数据范围

• $2 \le a,b \le 2 \times 10^9$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB