求逆元2

题目描述

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

输入

输入两个数a和p。

输出

输出满足同余方程的x。

样例

提示

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