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