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

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

int a, n;

int inv_mod(int a, int n)
{
    if(a % n == 0)
        return 0;
    long long x0 = inv_mod(n, a % n);
    return ((1 - x0 * n) / (a % n)) % n;
}

int main()
{
    fin >> a >> n;
    int rez = inv_mod(a, n);
    while(rez < 0)
        rez += n;
    fout << rez;
    return 0;
}