1507 - 求逆元2

通过次数

21

提交次数

32

Time Limit : 1 秒
Memory Limit : 128 MB

已知a和p,求正整数x使之满足ax≡1 mod p。p不一定是质数。如果有多个x,则输出最小的那个。如果无解,则输出"No solution"

Input

输入两个数a和p。

Output

输出满足同余方程的x。

Examples

Input

5 6

Output

5

Hint

对于100%的数据,1< a,p< 1e4。