#include<fstream>
#include<algorithm>
#include<iostream>
using namespace std;
unsigned long long int logput(unsigned long long int n, unsigned long long int p, unsigned long long int modul)
{
    unsigned long long int lgput = 1;
    unsigned long long int cur_power = 0;
    unsigned long long int squares = 1;
    unsigned long long int h = (n % modul);
    while(p != 0)
    {
        while(2 * cur_power + 1 <= p)
        {
            lgput = (lgput * h) % modul;
            cur_power = squares * 2 - 1;
            squares = squares * 2;
            h = ( h * h ) % modul;
        }
        p = p - cur_power;
        cur_power = 0;
        h = n;
        squares = 1;
    }
    return lgput;
}
bool Prim(unsigned long long int h)
{
    if(h == 2)
    {
        return 0;
    }
    if(h % 2 == 0)
    {
        return 1;
    }
    unsigned long long int radical;
    radical = sqrt(h);
    for(unsigned long long int i = 3 ; i <= radical + 1 ; i = i+2)
    {
        if(h % i == 0)
        {
            return 1;
        }
    }
    return 0;
}
unsigned long long int Phi(unsigned long long int n)
{
    unsigned long long int phi = n;
    unsigned long long int radical;
    radical = sqrt(n);
    for(unsigned long long int i = 2 ; i <= radical + 1 ; ++i)
    {
        if((Prim(i) == 0) && (n % i == 0))
        {
            phi = phi * (i-1) / i;
        }
    }
    if(Prim(n) == 0)
    {
        phi = n-1;
    }
    return phi;
}
int main()
{
    ifstream read("inversmodular.in");
    ofstream write("inversmodular.out");
    unsigned long long int a,n,exponent;
    read >> a >> n;
    exponent = Phi(n) - 1;
    write << logput(a,exponent,n);
    return 0;
}