1507 - 求逆元2
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。