#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
long long a,divi,n;

long long phi(long long n)
{

    long long rad,ok=0,i,sol=n,aux=n;
    rad=sqrt(n);
    for(i=2;i<=rad;i++)
    {

        if(n%i==0)
        {


            while(n%i==0)
                n/=i;
            sol=sol/n*(i-1);
        }

    }
    if(n!=1)
    {

        sol=sol/n*(n-1);
    }
    n=aux;
    return sol;

}

long long lgput(long long  baza, long long p)
{

    if(p==1)
        return baza;
    if(p%2==0)
        return lgput((baza*baza)%n,p/2);
    else return (baza*lgput(baza,p-1))%n;

}
int main()
{

    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    cin>>a>>n;
    divi=phi(n);
    cout<<lgput(a,divi-1);
    return 0;



}