#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int lgput(int a, int p, int mod)
{
    int res = 1;
    while(p > 0)
    {
        if(p % 2 == 1)
            res = (1LL * res * a) % mod;
        a = (1LL * a * a) % mod;
        p /= 2;
    }
    return res;
}
int f(int n)
{
    int r = 1, d = 2;
    while(n > 1)
    {
        int put = 0;
        while(n % d == 0)
        {
            n /= d;
            put ++;
        }
        if(put != 0)
            r *= 1LL * (d - 1) * lgput(d, put - 1, 20000000000000);
        d ++;
        if(n > 1 && d * d > n)
            d = n;
    }
    return r;
}
int32_t main()
{
    int a, n;
    in >> a >> n;
    out << lgput(a, f(n) - 1, n);
    return 0;
}