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

using namespace std;

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

ll a,n;

ll get(ll M)
{
    ll cr=M;
    for(ll i=2;i*i<=M;++i)
    {
        if(M%i==0)
        {
            while(M%i==0)
            {
                M/=i;
            }
            cr=(cr/i)*(i-1);
        }
    }
    if(M!=1)
    {
        cr=cr/M*(M-1);
    }
    return cr;
}

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

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