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

using namespace std;

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

ll a,n;

ll inv(ll N, ll M)
{
    ll nr=N,cr=1,put=M-2,p;
    for(p=1;p<=put;p<<=1)
    {
        if(p & put)
            cr=((long long)cr*nr)%M;
        nr=((long long)nr*nr)%M;
    }
    return cr;
}

int main()
{
    x>>a>>n;
    y<<inv(a,n);
    x.close();
    y.close();
    return 0;
}