#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");


long long val, MOD, inverse, coef;


void modular_inverse(long long a, long long b, long long &x, long long &y){
        if(b == 0){
            x = 1, y = 1;
        }
        else {
            long long x1, y1;
            modular_inverse(b, a % b, x1, y1);
            x = y1;
            y = x1 - a / b * y1;
        }
}

int main(){

    ios :: sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);

    fin >> val >> MOD;

    modular_inverse(val, MOD, inverse, coef);

    while(inverse < 0)
        inverse += MOD;

    fout << inverse;

    fin.close();
    fout.close();
    return 0;
}