#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++ )
    {
        int nr = 0;

        while(n%i == 0){
            n /=i;
            nr++;
        }
        if(nr>0){
            tot = tot - tot/i;
        }

    }

    return (tot ==n)?n-1: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;
}