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

using namespace std;

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

int64_t pow(int64_t x,int64_t y,int64_t n)
{
    int64_t m=1;
    while(y)
    {
        if(y&1)
        {
            m=(m*x)%n;
        }
        x=(x*x)%n;
        y>>=1;
    }

    return m;
}

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;
    f>>a>>n;
    t<<pow(a,psi(n)-1,n);
    return 0;
}