#include <fstream>

using namespace std;

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

int invmod(int a, int b)
{
    int x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1)
    {
        int q = a1 / b1;
        int 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()
{
    int a, m;
    cin >> a >> m;
    cout << invmod(a, m);
}