#include <bits/stdc++.h>

using namespace std;
#define int long long

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int phi(int n)
{
    if(n<=0) return 0;
    int sol=n;
    for(int d=2;d*d<=n;d++)
        if(n%d==0)
    {
        sol=sol/d*(d-1);
        while(n%d==0)
            n/=d;
    }
    if(n>1)
        sol=sol/n*(n-1);
    return sol;
}
int fastpow(int a, int b, int mod)
{
    int rez=1;
    while(b)
    {
        if(b%2==1)
            rez=(rez*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return rez;
}
int inv(int a, int b)
{
    return fastpow(a,phi(b)-1,b);
}
signed main()
{
    int a,b;
    f>>a>>b;
    g<<inv(a,b);
    return 0;
}