#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int a,b,r,n1,m1,n2,m2,m,n,c,c1,cnt,rez,r1,b2;
int main()
{
        cin>>a>>b;
        b2=b;
        rez=1;
        cnt=1;
        c1=a/b;
        r1=a%b;
        if(r1==0)
            cout<<rez/b;
        else
        {
        while(b != 0)
        {
            r=a%b;
            c=a/b;
            if(cnt==1)
            {
                m1=1;
                n1=-c;
            }
            else if(cnt==2)
            {
                m2=-c;
                n2=1+c1*c;
            }
            else
            {
                m=m1-m2*c;
                n=n1-n2*c;
                m1=m2;
                n1=n2;
                m2=m;
                n2=n;
            }
            a=b;
            b=r;
            cnt++;
        }
        m1=rez/a*m1;
        n1=rez/a*n1;
        while(m1<0)
            m1+=b2;
        cout<<m1;
        }

    return 0;
}