#include <fstream>

using namespace std;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

typedef long long num;

num invmod(num a, num b)
{
    num x = 1, y = 0;
    num x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1)
    {
        num q = a1 / b1;
        num aux = x1;
        x1 = x - q * x1;
        x = aux;
        aux = y1;
        y1 = y - q * y1;
        y = aux;
        aux = b1;
        b1 = a1 - q * b1;
        a1 = aux;
    }
    return (x + b) % b;
}

int main()
{
    num a, m;
    cin >> a >> m;
    cout << invmod(a, m);
}