#include <iostream>
#include <fstream>
using namespace std;
int v[100];
void cmmdc(int &a, int b,int &k)
{
    int r;
    while(b)
    {
        r=a%b;
        v[++k]=a/b;
        a=b;
        b=r;


    }

}

int main()
{
    int n,a,k;
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");

        fin>>a>>n;
        k=0;
        cmmdc(a,n,k);
        int x=1;
        int y=0;

        for(int l=k;l>=1;l--)
        {
            int x0=x;
            x=y;
            y=x0-v[l]*y;
        }
        if(x<0)
            x=x+n;
        fout<<x;




    return 0;
}