#include <bits/stdc++.h>

using namespace std;

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

int a, n;
long long nr = 1;

long long putere(long long a, long long b, long long mod)
{
    long long r = 1;
    while(b > 0)
    {
        if(b % 2 == 1)
            r = (r * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return r;
}

long long Euler(long long x)
{
    long long d = 2;
    int p;
    bool intra = 0;
    while(d * d <= x)
    {
        if(x % d == 0)
        {
        p = 0;
        intra = 1;
        while(x % d == 0)
        {
            x /= d;
            p++;
        }
        nr *= ((d - 1) * putere(d, p - 1, n + 1000));
        }
        d++;
    }
    if(intra == 0) return x - 1;
    else return nr;
}
int main()
{
    fin>>a>>n;
    long long x = Euler(n);
    fout<<putere(a, x - 1, n);
    return 0;
}