#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long MOD = 0;
long long exponentiere(long long a, long long n)
{
    long long r = 1;
    a = a % MOD;
    while(n)
    {
        if(n % 2 == 1)
        {
            r = r * a % MOD;
        }
        a = a * a % MOD;
        n = n / 2;
    }
    return r % MOD;
}
int Phi(int n)
{
    int p = n, d = 2;
    while(n > 1)
    {
        if(n%d == 0)
        {
            p = p / d * (d-1);
            while(n%d == 0)
            {
                n/=d;
            }
        }
        d++;
        if(d * d > n)
        {
            d=n;
        }
    }
    return p;
}
int main()
{
    long long a, n, x;
    cin >> a >> n;
    MOD = n;
    x  = Phi(n);
    if(x == n - 1)
    {
        cout << exponentiere(a, n - 2) % MOD;
    }
    else cout<<(exponentiere(a, x)) % MOD;
    return 0;
}