/*
    FORMULA : InvMod(A, N) = A ^ phi(N)
**/

#include <iostream>
#include <fstream>
#define ull unsigned long long

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

ull lgput(ull a, ull b, ull mod)
{
    ull r = 1;
    while(b)
    {
        if(b % 2 == 1)
            r = ( r % mod * a % mod ) % mod;
        a = ( a % mod * a % mod ) % mod;
        b /= 2;
    }
    return r;
}
ull phi(int n)
{
    ull p = 1, d = 2, fm;
    do
    {
        fm = 0;
        while(n % d == 0)
        {
            n /= d;
            fm ++;
        }
        if(fm > 0)
        {
            p = p * (d - 1) * lgput(d, fm - 1, d);
        }
        d ++;
        if(d * d > n && n > 1)
        {
            p = p * (n - 1);
            n = 1;
        }
    }while(n > 1);
    return p;
}
int main()
{
    int a, n;
    f >> a >> n;
    g << lgput(a, phi(n) - 1, n);
    return 0;
}