#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) tot -= tot/i;;
         while(n%i == 0 && n!=1)
                n /=i;

    }

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