#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-n/i;
            while (n%i==0)
                n=n/i;
        }
    val--;
    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;
    return ((ax*ax2*ax2)%n);
}
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;
}