#include <iostream>
#include <fstream>

using namespace std;

ifstream q("inversmodular.in");
ofstream w("inversmodular.out");

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

int euclid(int a,int b)
{
    if(b==0) return a;
    euclid(b,a%b);
}

int main()
{long long a,n;
    q>>a>>n;
    auto t = euclidExtins(a,n);
    int k = t.first;
    while(k<0) k+=n;
    w<<k;

    return 0;
}