#include<bits/stdc++.h> using namespace std; long long extended_gcd(long long a,long long b,long long &x,long long &y){ if(b==0){ x=1; y=0; return a; } long long x1,y1; long long gcd=extended_gcd(b,a%b,x1,y1); x=y1; y=x1-(a/b)*y1; return gcd; } long long mod_inverse(long long a,long long b){ long long x,y; extended_gcd(a,b,x,y); return(x%b+b)%b; } int main(){ long long a,b; cin>>a>>b; cout<<mod_inverse(a,b)<<endl; return 0; }