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