#include "inv.h"

constexpr int INIT_BOUND = 4000000;
constexpr int P = 998244353;

int _inv[INIT_BOUND];

void init(int p) {
    _inv[1] = 1;
    for (int i = 2; i < INIT_BOUND; i ++) {
        _inv[i] = (long long){p - p / i} * _inv[p % i] % p;
    }
}

int inv(int x) {
    int ret = 1;

    while (x >= INIT_BOUND) {
        int y = P % x;
        if (y << 1 <= x) {
            ret = (long long){P - P / x} * ret % P;
            x = y;
        } else {
            ret = (P / x + 1ll) * ret % P;
            x = x - y;
        }
    }

    return (long long){ret} * _inv[x] % P;
}