#include <bits/stdc++.h>
using namespace std;
inline void euclid(long long &x , long long &y, long long a , long long b)
{
    if (b == 0)
        x = 1 , y = 0;
    else
    {
        euclid(x , y, b, a % b);
        long long aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    long long x , MOD;
    scanf("%lld %lld", &x, &MOD);
    long long inv = 0 , ins = 0;
    euclid(inv , ins , x, MOD);
    if(inv < 0) inv = MOD + inv % MOD;
    printf("%lld\n", inv);
    return 0;
}