#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.in");
int LogP(int a, int n,int mod)
{
   int p=1;
   while(n)
   {
       if(n%2==1)
        p=1LL*p*a%mod;
       n/=2;
       a=1LL *a*a%mod;
   }
   return p;
}
int phi(int n)
{
    int p,sol;
    sol=n;
    p=2;
    for(p = 2;n>1 && p*p<=n;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 main()
{
    int a,n;
    fin >> a >> n;
    int phii;
    phii=phi(n);
    fout<<LogP(a,phii-1,n)<<"\n";
    return 0;
}