#include <fstream>

using namespace std;

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

using ll = long long;

ll A, N;

ll fastpow(ll n, ll p)
{
    ll b = n;
    ll ans = 1;

    for(int i = 0; (1 << i) <= p; i ++)
    {
        if((1 << i) & p)
            ans =(1LL * ans * b) % N;
        b =(1LL * b * b) % N;
    }
    return ans;
}

int main()
{
    fin >> A >> N;
    fout << fastpow(A, N - 2);
    return 0;
}