#include <bits/stdc++.h>
#define nat long long
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a, n;

int Phi(int n)
{
    int sol=n;
    int p;
    for(p=2; p*p<=n && n>1;p++)
    {
        if(n%p==0)
            sol=sol/p*(p-1);
        while(n%p==0)
            n/=p;
    }
    if(n>1)
        sol=sol/n*(n-1);
    return sol;
}
int LogP(int a,int n,int Mod)
{
    int p=1;
    while(n>0)
    {
        if(n%2==1)
            p=1LL*p*a%Mod;
        n/=2;
        a=a*a%Mod;
    }
    return p;
}
int main()
{
    fin >>a>>n;
    Phi=Phi(n);
    fout<<LogP(a,Phi-1,n)<<endl;
    fin.close();
    fout.close();
}