#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");

inline void gcd (long long &inv , long long &var,int a,int b)
{
    if(not b)
        inv = 1, var = 0;
    else
    {
        gcd(inv,var,b , a % b);
        long long aux = inv;
        inv = var;
        var = aux - var * (a / b);
    }
}

int main()
{
    long long inv = 0,var; int n,mod;
    f >> n >> mod;

    gcd(inv , var , n , mod);

    if(inv <= 0)
        inv = mod + inv % mod;

    g << inv;
    return 0;
}