#include <fstream>
using namespace std;

ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");

int Euclid (int numar_1 , int numar_2 , int &factor_1 , int &factor_2 , int mod)
{
    if (!numar_2) { factor_1 = 1; factor_2 = 0; return numar_1; }
    int factor_3 , factor_4 , cmmdc = Euclid(numar_2 , numar_1 % numar_2 , factor_3 , factor_4 , mod);
    factor_2 = (factor_3 - 1LL * numar_1 / numar_2 * factor_4 % mod + mod) % mod;
    factor_1 = factor_4;
    return cmmdc;
}

int InversModular (int numar , int mod)
{
    int invers , factor;
    Euclid(numar , mod , invers , factor , mod);
    return (1LL * invers + mod) % mod;
}

int main ()
{
    int numar , mod;
    cin >> numar >> mod;
    cout << InversModular(numar , mod);
    cout.close(); cin.close();
    return 0;
}