#include <fstream>
using namespace std;
#define IN "inversmodular.in"
#define OUT "inversmodular.out"

ifstream fin(IN);
ofstream fout(OUT);

int a, n;

void citire();
void ext(int&, int&, int, int);

int main(){
    citire();
    int inv=0, ins;
    ext(inv, ins, a, n);
    
    if (inv<0)
        inv+=n;
    
    fout <<inv<<'\n';
    fout.close();
    return 0;
}

void ext(int &x, int &y, int a, int b){
    if (!b){
        x=1; y=0;
        return;
    }
    ext(x, y, b, a%b);
    int aux=x;
    x=y;
    y=aux-y*(a/b);
}

void citire(){
    fin >>a>>n;
}