#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f ("inversmodular.in");
ofstream t ("inversmodular.out");

int64_t psi(int64_t n)
{
    int64_t res = n;
    vector <int> primes;
    for(int i = 2 ; i*i <= n ; i++)
    {
        if(n%i == 0)
            primes.push_back(n/i);
        while(n%i == 0)
            n /= i;
    }
    for(const auto& prim :primes)
        res -= res/prim;
    if(n>1)
        res -= res/n;
    return res;
}

int main()
{
    int64_t a,n,aux,m=1;
    f>>a>>n;
    aux=psi(n)-1;
    while(aux)
    {
        if(aux&1)
        {
            m=(m*a)%n;
        }
        a=(a*a)%n;
        aux>>=1;}
    t<<m;
    return 0;
}