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

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

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

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

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