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

using namespace std;

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

#define ull 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){
            while(n%i == 0)
                n /=i;
            tot -= tot/i;
        }

    }

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

    return tot;

}

int main ( )
{
    ull a,n;
    in>>a>>n;

    ull powertot = totient(n)-1;

    ull modulo = n;
    ull base=a,res=1;

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

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

    return 0;
}