#include <bits/stdc++.h>

using namespace std;

int cmmdc(int a,int b,int &u,int &v)
{
    if(b==0){u=1;v=0;return a;}
    int ut,vt,d;
    d=cmmdc(b,a%b,ut,vt);
    u=vt;
    v=ut-(a/b)*vt;
    return d;
}

int main()
{
    int a=0,n=0,x=0,y=0,d=0;
    ifstream fi("inversmodular.in");
    fi>>a>>n;
    fi.close();
    d=cmmdc(a,n,x,y);
    x=x%n;
    if(x<0)x=x%n+n;
    ofstream fo("inversmodular.out");
    fo<<x;
    fi.close();
    return 0;
}