#include <fstream>
#include <cmath>

#define ll long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
ll a, n;

ll pow(ll a, ll p)
{
    if(p == 1)
        return a % n;

    ll rez = pow(a, p / 2);
    rez = rez * rez % n;
    if(p % 2 == 0)
        return rez;
    else
        return rez * a % n;
}

int main()
{
    fin >> a >> n;

    ll nr = n;
    for(int i = 2; 1LL * i * i <= n; i ++)
        if(n % i == 0)
        {
            while(n % i == 0) n /= i;
            nr = nr - nr / i;
        }
    if(n != 1)
        nr = nr - nr / n;

    fout << pow(a, nr - 1);
    return 0;
}