#include <bits/stdc++.h>
using namespace std;

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

int main(void){
    int y0 = 0, y1 = 1;
    int M;
    int aux = M;
    int r,c,y;
    int a;
    in >> a;
    in >> M;
    while (a != 0)
    {
        r = M % a;
        c = M / a;
        M = a;
        a = r;
        y = y0-c*y1;
        y0 = y1;
        y1 = y;
    }

    while (y0 < 0)
    {
        y0 += aux;
    }
    out << y0;
}