#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <tuple>
#include <limits>
#include <functional>
#include <complex>
#include <bitset>
#include <list>

//#include <atomic>
//#include <condition_variable>
//#include <future>
//#include <mutex>
//#include <thread>

using namespace std;

#define debug(x) cerr << #x << " = " << x << "\n"

const int INF           = 0x3f3f3f3f;
const long long INFL    = 0x3f3f3f3f3f3f3f3fLL;

template<int MOD>
struct ModInt 
{
    static const int Mod = MOD;
    unsigned x;
    ModInt() : x(0) { }
    ModInt(signed sig) { int sigt = sig % Mod; if (sigt < 0) sigt += MOD; x = sigt; }
    ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
    int get() const { return (int) x; }

    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long) x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

    ModInt inverse() const 
    {
        signed a = x, b = Mod, u = 1, v = 0;
        while (b) 
        {
            signed t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        if (u < 0) u += Mod;
        ModInt res; res.x = (unsigned) u;
        return res;
    }
};

int main(int argc, char* argv[]) 
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    cin.sync_with_stdio(false);
    int N, A;
    cin >> N >> A;
    signed a = N, b = A, u = 1, v = 0;
    while (b)
    {
        signed t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    if (u < 0) u += A;
    cout << u << "\n";
    return 0;
}