#include <bits/stdc++.h>

using namespace std;

int A, MOD;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void EuclidExtins(int a, int b, int& x, int& y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }

    int x1, y1;
    EuclidExtins(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
}

int InversModular(int A)
{
    int X, Y;
    EuclidExtins(A, MOD, X, Y);
    if(X < 0) X += MOD;

    return X;
}

void ReadInput()
{
    cin >> A >> MOD;
}

int main()
{
    SetInput("inversmodular");

    ReadInput();
    cout << InversModular(A) << '\n';

    return 0;
}