题目描述

给定两个正整数 $a$ 和 $b$，求满足同余方程

的最小正整数解 $x_0$。输入数据保证方程一定有解（即 $\gcd(a,b)=1$）。

输入格式

一行，两个正整数 $a,\ b$，用一个空格隔开。

输出格式

一行，一个正整数 $x_0$，即最小正整数解。

样例

3 10

7

说明/提示

$x$ 称为 $a$ 对模 $b$ 的乘法逆元。可用扩展欧几里得算法求出一组满足 $a\cdot x + b\cdot y = 1$ 的 $(x, y)$，再把 $x$ 调整到 $[1, b-1]$ 区间内即可。也可使用费马小定理 $x = a^{b-2} \bmod b$（当 $b$ 为质数时）。