给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

Input

输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)

Output

输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

Input示例

2 3

Output示例

2

 

参见挑战程序设计第115页：

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll extgcd( ll a,ll b,ll &x,ll &y){
	ll d=a;
	if(b){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
	else {
		x=1;y=0;
	}
	return d;
}
ll modinv(ll a,ll mod){
	ll x,y;
	extgcd(a,mod,x,y);
	return (mod+x%mod)%mod;
}
int main(){
	ll m,n;
	cin>>m>>n;
    cout<<modinv(m,n)<<endl;
	return 0;
}