#include <bits/stdc++.h>

using namespace std;

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

int n, a;

int Phi(int n)
{
    int d, p;
    d = 2;
    p = n;
    if(n % d == 0)
    {
        p = p / 2;
        while(n % d == 0)
            n /= d;
    }
    d = 3;
    while(n > 1 && d * d <= n)
    {
        if(n % d == 0)
        {
            p = p / d * (d - 1);
            while(n % d == 0)
                n /= d;
        }
        d += 2;
    }
    if(n > 1)
        p = p / n * (n - 1);
    return p;
}

int Putere(int a, int n, int MOD)
{
    int p;
    p = 1;
    while(n > 0)
    {
        if(n % 2 == 1)
        {
            n--;
            p = (1LL * p * a) % MOD;
        }
        n /= 2;
        a = (1LL * a * a) % MOD;
    }
    return p;
}

int main()
{
    int phi;
    fin >> a >> n;
    phi = Phi(n);
    fout << Putere(a, phi - 1, n);
    fin.close();
    fout.close();
    return 0;
}