#include <bits/stdc++.h>

using namespace std;

long long A;
int N;

long long Pow_Log(long long a,int n)
{
    long long sol;
    sol = 1;
    while(n >= 1)
    {
        if(n % 2 == 1)
        {
            sol = (sol * a) % N;
            n--;
        }
        n /= 2;
        a = (a * a) % N;
    }
    return sol;
}

int main()
{
    ifstream fin("inversmodular.in");
    fin>>A>>N;
    fin.close();
    ofstream fout("inversmodular.out");
    fout<<Pow_Log(A,N-2)<<"\n";
    fout.close();
    return 0;
}