#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=1;
    rad=sqrt(n);
    for(i=2;i<=rad;i++)
    {

        if(n%i==0)
        {
            ok=1;
           // p=n/i;
            sol=sol*(n/i)*(i-1);
            while(n%i==0)
                n/=i;

            rad=sqrt(n);
        }

    }
    if(n!=1)
    {

        sol=sol*(n-1);
    }
    if(ok==0)
        sol=n-2;

    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);
    return 0;



}