#include <fstream>
#include <vector>
using namespace std;

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

long long n, a;

bool isPrime(long long n)
{
    for(int i = 2; i*i<=n; i++)
        if(n%i==0)
            return false;
    return true;
}

long long power(long long baza, long long exp)
{
    long long rez = 1;
    while(exp!=0)
    {
        if(exp%2==0)
        {
            baza = (baza * baza);
            exp/=2;
        }
        else
        {
            rez = (rez * baza);
            exp--;
        }
    }
    return rez;
}

int main()
{
    in>>a>>n;
    if(isPrime(n))
        out<<power(a, n-2) % n;
    else
    {
        int ok;
        long long cn, phi, d = 2;
        while(cn!=1)
        {
            ok = 0;
            while(cn%d==0)
            {
                cn/=d;
                ok = 1;
            }
            if(ok)
                phi*=(1-1/d);
            if(d==2) d=3;
            else d+=2;
        }
        out<<power(a, phi-1) % n;
    }
    return 0;
}