#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cstring>

using namespace std;

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

#define ull unsigned long long int

int mod(ull a, ull b, ull modulo )
{
    return ((a%modulo)*(b%modulo))%modulo;

}

int totient(ull n)
{
    int tot =n;
    for(ull i =2 ; i*i <= n ; i++ )
    {
        if(n%i==0)
            tot -= tot/i;
        while(n%i == 0)
            n /=i;

    }

    if (n > 1)
        tot -=tot/n;

    return tot;

}

int main ( )
{
    ull  a,n,modulo,base=a,res=1 ;

    in>>base>>n;
    modulo = n;
    ull powertot = totient(n)-1;

    while(powertot)
    {
        if(powertot&1)
            res= mod(res,base, modulo);

        base = mod(base,base, modulo);
        powertot >>=1;
    }
    out<<res;

    return 0;
}