#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int Putere(int a, int n,int MOD)
{
    int P = 1;
    while (n>0)
    {
        if (n % 2 == 1)
            P = 1LL* P * a % MOD;
        a = 1LL*a * a % MOD;
        n /= 2;
    }
    return P;
}
int Phi(int n)
{
    int p = n;
    for(int f=2;f*f<=n;f++)
    {
        if(n % f == 0)
        {
            p = p / f * (f-1);
            while (n % f == 0)
                n /= f;
        }
    }
    if (n > 1)
        p = p / n * (n - 1);
    return p;
}
int main()
{
    int a, n;
    fin >> a >> n;
    fout << Putere(a, Phi(n) - 1, n);
    return 0;
}