#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int q[10000], n, a, b, c, z=0, aux, x, y;
    fin >> a >> b;
    n=b;
    while(b)
    {
        q[++z]=a/b;
        aux=b;
        b=a%b;
        a=aux;
    }
    x=1;
    y=0;
    for (int i=z; i>=1; i--)
    {
        aux=y;
        y=x-q[i]*y;
        x=aux;
    }
    while(x<0)
        x+=n;
    fout << x;
    return 0;
}