#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 gcd(ull a, ull b)
{
    return (b==0)?a:gcd(b, a%b);
}



int totient(ull n)
{
    int tot =0;
    for(int i =1 ; i < n ; i++ )
    {
        if (gcd(i,n) == 1)
        {
            tot++;
        }

    }
    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= (res*base)%modulo;

        base = (base*base)%modulo;
        powertot >>=1;
    }
    out<<res;

    return 0;
}