#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n;
long long int putere(int,int);
int Phi(int);
int main()
{
    fin>>a>>n;
    fout<<putere(a,Phi(n)-1)<<'\n';
    return 0;
}

int Phi(int x)
{int d,rez;
 for(d=2,rez=1; d*d<=x; d++)
     if(x%d==0)
        {while(x%d==0)
            {x/=d;
             rez*=d;
            }
        rez/=d;
        rez*=(d-1);
        }
 if(x>1) rez*=(x-1);
 return rez;
}

long long int putere(int x,int y)
{
 long long int p;
 if(y==0) return 1;
 if(y%2==1) return (x*putere(x,y-1))%n;
 p=putere(x,y/2);
 return (p*p)%n;
}