#include <fstream>
//#include <iostream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int m;
int putere(int x, int n)
{
    int p=1;
    while(n>0)
    {
        if(n%2==1)
        {
            p=p*x%m;
            n--;
        }
        x*=x;
        n/=2;

    }
    return p;
}
int euler(int nr)
{
    int sol=1,pt=0;
    for(int i=2; i<=nr; i++)
    {
        if(nr%i==0)
        {
            pt=0;
            while(nr%i==0)
            {
                pt++;
                nr/=i;
            }
            sol*=putere(i,pt-1);
            sol*=(i-1);
            //cout<<i<<" "<<pt<<endl;
        }
    }
    return sol;
}
int main()
{
    int a,n,put;
    in>>a>>n;
    m=n;
    put=euler(n);
    //cout<<a<<" "<<put-1<<endl;
    out<<putere(a,put-1)%m;
    return 0;
}