#include <iostream>
#include <fstream>

using namespace std;

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

long long inversModular(long long a, long long n)
{
    long long s0 = 1, s1 = 0, r0 = a, r1 = n, r2 = 0, s2 = 0;
    
    while (r1 != 0)
    {
        long long q = r0 / r1;

        r2 = r0 - q * r1;
        r0 = r1;
        r1 = r2;

        s2 = s0 - q * s1;
        s0 = s1;
        s1 = s2;
    }

    if (s0 < 0)
    {
        s0 = (s0 % n + n) % n;
    }

    return s0;
}

int main()
{
    long long a, n;


    fin >> a >> n;

    fout << inversModular(a, n) << '\n';

    return 0;
}