#include <bits/stdc++.h>

using namespace std;

const string FILENAME = "inversmodular";

ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");

int a, n;

int phi(int n)
{
    int sol = n;
    for(int i = 2; n > 1 && i * i <= n; i++)
        if(n % i == 0)
        {
            while(n % i == 0)
                n /= i;
            sol -= sol / i;
        }
    if(n > 1)
        sol -= sol / n;
    return sol;
}

int exp(int a, int n, int mod)
{
    long long p = 1;
    while(n)
    {
        if(n & 1)
            p = 1ll * p * a % mod;
        a = 1ll * a * a % mod;
        n >>= 1;
    }
    return p;
}

int main()
{
    fin >> a >> n;
    fout << exp(a, phi(n) - 1, n) << "\n";
    fin.close();
    fout.close();
    return 0;
}