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

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

typedef unsigned long long mare;

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

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

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