#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int euler(int x)
{
    int ans = x;
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0)
        {
            while(x % i == 0)
                x /= i;
            ans -= ans / i;
        }
    if(x > 1)
        ans -= ans / x;
    return ans;
}

int fastPow(int a, int exp, int mod)
{
    int ans = 1;
    while(exp)
    {
        if(exp & 1)
            ans = (1LL * ans * a) % mod;
        a = (1LL * a * a) % mod;
        exp >>= 1;
    }
    return ans;
}



int InversModular(int a, int n)
{
    int phi = euler(n);
    return fastPow(a, phi - 1, n);// a^ (phi(n) - 1) mod n
}


int main() {
    int a, n;
    fin >> a >> n;
    fout << InversModular(a, n);

    fin.close();
    fout.close();

    return 0;
}