#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) % n;
            exp/=2;
        }
        else
        {
            rez = (rez * baza) % n;
            exp--;
        }
    }
    return rez;
}

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