#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

long long invers(long long n)
{
    long long e=n;
    long long d=2;
    while(d*d<=n)
    {
        if(n%d==0)
        {
            e=e/d*(d-1);
            while(n%d==0)
                n=n/d;
        }
        d++;
    }
    if(n!=1)
        e=e/n*(n-1);
    return e;
}

long long lgput(long long a,long long n,long long mod)
{
    long long total=1;
    while(n!=0)
    {
        if(n%2!=0)
        {
            total=total*a%mod;
        }
        a=a*a%mod;
        n=n/2;
    }
    return total;
}

int main()
{
    long long a,n,nr;
    fin>>a>>n;
    nr=invers(n);
    fout<<lgput(a,nr-1,n);
    return 0;
}