#include<bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a,b;
int inv_mod(int a, int b)
{
    int x=0, y=0, z=1, r=0, c=0;
    int cop=b;
    while(a)
    {
        r=b%a;
        c=b/a;
        a=b;
        b=c;
        x=y-c*z;
        y=z;
        z=x;
    }
    while(y<0) y+=cop;
    return y;
}
int main()
{
    f>>a>>b;
    g<<inv_mod(a,b);
    return 0;
}