#include <fstream>

#define ll long long

using namespace std;

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

ll a, n, tmp;

ll get_tmp()
{
    int s = n, c = n;
    for(ll i = 2; i * i <= n; ++i)
    {
        if(c % i == 0)
        {
            s = s - s / i;
            while(c % i == 0)
                c = c / i;
        }
    }
    if(c != 1)
        s = s - s / c;

    return s;
}

ll put()
{
    ll meh = a;
    a = 1;

    while(tmp > 0)
    {
        if(tmp % 2 == 1)
        {
            a = a * a;
            a = a % n;
            tmp--;
        }
        meh = meh * meh;
        meh = meh % n;
        tmp = tmp / 2;
    }
    return a;
}

int main()
{
    in >> a >> n;
    tmp = get_tmp() - 1;
    out << put();
}