#include <fstream>
std::ifstream f("inversmodular.in");
std::ofstream g("inversmodular.out");
void E(int a,int b,int &x,int &y) {
    if (b==0) {
        x=1,y=0;
        return;}
    int xx, yy;
    E(b,a%b,xx,yy);
    y = xx-(a/b)*(x=yy);}
int main() {
    int x=0,y=0,n,mod;
    f>>n>>mod;
    E(n,mod,x,y);
    if (x<0) x+=mod;
    g<<x;
}