#include <iostream>
#include <fstream>
#define LL long long

using namespace std;

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

LL phi(LL x)
{
    LL ans = x;

    for(LL i = 2LL; i * i <= x; i++)
    {
        if(x % i == 0LL)
        {
            while(x % i == 0LL)
                x /= i;
            ans = (ans / i) * (i - 1LL);
        }

        //cout << i << ' ' << ans << '\n';
    }

    if(x != 1)
        ans = (ans / x) * (x - 1LL);

    //cout << ans << '\n';

    return ans;
}

LL logPow(LL x, LL p, LL mod)
{
    //cout << "GOT HERE!\n";
    LL ans = 1;

    while(p > 0)
    {
        if(p & 1)
            ans = ((ans % mod) * (x % mod)) % mod;

        p >>= 1;
        x = ((x % mod) * (x % mod)) % mod;
    }

    return ans;
}

int main()
{
    LL a, n;
    in >> a >> n;

    out << logPow(a, phi(n) - 1, n);

    return 0;
}