#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

int n, k;

void euclid(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;

    } else {
        ll xx, yy;
        euclid(b, a%b, xx, yy);
        x = yy;
        y = xx - (a/b) * yy;
    }
}

ll inv(ll a, ll mod){
    ll inv, temp;
    euclid(a, mod, inv, temp);
    if(inv < 0)
        inv += mod;
    return inv;
}

int main()
{
    fin >> n >> k;
    fout << inv(n, k);
    return 0;
}