#include <bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

pair<long long, long long> invers_mod( long long a, long long b )
{
    if( b == 0 )
        return {1, 0};
    else
    {
        pair<long long, long long> p;
        p = invers_mod(b, a%b);
        return {p.second, p.first - (a/b)*p.second};
    }
} 

int main() {
	long long a, M, inv;
    f >> a >> M;
    inv = invers_mod(a, M).first;
    g << (inv % M + M) % M;
}