//#include <iostream>
#include <fstream>
using namespace std;

#define ull unsigned long long

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

bool prim(ull n)
{
    if(n == 2)
        return true;

    if(n < 2 || n % 2 == 0)
        return false;

    for(ull d=3; d*d<=n; d++)
    {
        if(n % d == 0)
            return false;
    }

    return true;
}

ull power(ull a, ull n, const ull mod)
{
    ull p = 1;
    while(n)
    {
        if(n % 2 == 1)
            p *= a, p %= mod;

        a *= a;
        n /= 2;
    }

    return p;
}

int main()
{

    ull a, x, n, i, p = 1;
    cin>>a>>n;

    if(prim(n)) p = n - 1;

    x = power(a, p-1, n);

    cout<<x;

    return 0;
}