#include <fstream>
using namespace std;

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

//invers modular I - phi(n)
//euler -> a^phi(n) = 1 (mod n), gcd(a, n) = 1

typedef unsigned long long mare;

int phi(int n)
{
    int rez = n;
    int d;
    for (d = 2; d*d<=n; d++)
        if (n%d == 0)
        {
            rez = rez / d * (d-1);
            while (n%d == 0)
                n = n/d;
        }
    if (n > 1)
        rez = rez / n * (n-1);
    return rez;
}

int invmod(int a, int n)
{
    //a^-1 % n
    int e = phi(n)-1;
    mare b = a, rez = 1;
    while (e > 0)
    {
        if (e&1)
            rez = rez * b % n;
        b = b*b % n;
        e >>= 1;
    }
    return rez;
}

int main()
{
    int a, n;
    fin >> a >> n;
    fout << invmod(a, n);
    return 0;
}