// inv.cpp
// inv.h
#define once

void init(int p);
int inv(int x);

#include "inv.h"

namespace {
    int mod;
}

void init(int p) {
    mod = p;
}

// 扩展欧几里得算法求逆元
int extGCD(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = extGCD(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - (a / b) * y;
    return gcd;
}

int inv(int x) {
    int invX, y;
    extGCD(x, mod, invX, y);
    invX = (invX % mod + mod) % mod;  // 确保逆元为正数
    return invX;
}