#include <fstream>
#define ll long long

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long n, a, phi, inv;

ll get_phi(ll n){
    ll x = n;
    ll d = 2;
    ll p = 0;
    for(ll d = 2; d * d <= n; ++ d){
        if(!(n % d)){
            x /= d;
            x *= (d - 1);
        }

        while(!(n % d))
            n /= d;
    }
    if(n > 1){
        x /= n;
        x *= n - 1;
    }
    return x;
}

ll log_pow(ll x, ll pow){
    ll nr = 1;
    while(pow > 1){
        if(pow % 2){
            nr = (nr * x) % n;
            -- pow;
        }
        x = (x * x) % n;
        pow /= 2;
    }
    return (x * nr) % n;
}

int main()
{
    f>>a>>n;
    phi = get_phi(n);
    inv = log_pow(a, phi - 1);
    g<<inv;
    return 0;
}