#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    long long sol, q, a, n;
    f >> a >> n;
    gcd(sol, q, a, n);
    if(sol <= 0) sol += n;
    sol %= n;
    g << sol << "\n";
}