#include <iostream>
#include <fstream>
using namespace std;

//nerecursiv
int invmod(int a,int b)
{
    int q[100],nc=0,x,y,r,x1,y1,b1=b;
    while(b)
    {
        q[++nc]=a/b;
        r=a%b;
        a=b;
        b=r;
    }
    x=1;y=0;
    while(nc)
    {
        x1=y;
        y1=x-q[nc]*y;
        x=x1;
        y=y1;
        nc--;
    }
    //in c++   daca un numar tz este negativ, shi b pozitiv
    //              tz%b este tot negativ
    //          shi se calculeaza ca shi cum am luat -abs(tz)%b
    //Ex:    -254 % 10 -> -4
    return (b1+x%b1)%b1;
}

//recursiv
void invmodr(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;y=0;
    }
    else
    {
        int q=a/b;
        invmodr(b,a%b,x,y);
        int x1=y,y1=x-q*y;
        x=x1;y=y1;
    }
}



int main()
{ int a,b;
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>a>>b;
    g<<invmod(a,b);
    return 0;
}