#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("inversmodular.in");

ofstream fout("inversmodular.out");

int x, MOD;

void Euclid(int a, int b, int &x, int &y){

    if(b == 0)

        x = y = 1;

    else {

        int x1, y1;

        Euclid(b, a % b, x1, y1);

        x = y1;

        y = x1 - a / b * y1;

    }

}

int Modular_Inverse(int a, int MOD){

    int x, y;

    Euclid(a, MOD, x, y);

    while(x < 0)

        x += MOD;

    return x;

}

int32_t main(){

    fin >> x >> MOD;

    fout << Modular_Inverse(x, MOD) << "\n";

}