#include <iostream>
#include <fstream>
using namespace std;
#define ll long long
ll a,n,phi;
ll fphi(ll n)
{
    ll i;
    ll val=n;
    for (i=2;i*i<=n;i++)
        if (n%i==0)
        {
            val=val*(i-1)/i;
            while (n%i==0)
                n=n/i;
        }
    if (n!=1)
        val=val*(n-1)/n;
    return val;
}
ll power(ll base,ll exp)
{
    if (exp==0)
        return 1;
    ll ax;
    if (exp%2==1)
        ax=base;
    else
        ax=1;
    ll ax2=power(base,exp/2)%n;
    ll ax3=(ax2*ax2)%n;
    ax3=(ax3*ax)%n;
    return ax3;
}
int main(void)
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>a>>n;
    phi=fphi(n);
    g<<power(a,phi-1);
    f.close();
    g.close();
    return 0;
}