#include <fstream>

using namespace std;

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

long long n, a, phi, inv;

int get_phi(int n){
    int x = n;
    int d = 2;
    int p = 0;
    while(n > 1){
        if(!(n % d)){
            x /= d;
            x *= (d - 1);
        }

        while(!(n % d))
            n /= d;
        ++ d;
    }
    return x;
}

int log_pow(int x, int pow){
    int 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;
}