#include <iostream> using namespace std; long long extended_gcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long x1, y1; long long gcd = extended_gcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return gcd; } long long mod_inverse(long long a, long long b) { long long x, y; extended_gcd(a, b, x, y); return (x % b + b) % b; } int main() { long long a, b; cin >> a >> b cout << mod_inverse(a, b) << endl; return 0; }