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


ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int invMod(int a, int n) {
    int y0 = 0, y1 = 1;
    int aux = n;
    while(a!=0){
        int r = n%a;
        int c = n/a;
        n = a;
        a = r;
        int y = y0 - c*y1;
        y0 = y1;
        y1 = y;
    }
    while(y0<0){
        y0+=aux;
    }
    return y0;
}


int main()
{
    int A = 0 , N = 0;
    f>>A>>N;
    g<<invMod(A,N);
    f.close();
    g.close();
    return 0;
}