#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "inv.h"
using namespace std;
constexpr int N = 1e8;
int v[N], P;
void init(int p) {
	P = p;
	v[1] = 1;
	for (int i = 2; i < N; i++) {
		v[i] = P - 1ll * v[P % i] * (P / i) % P;
	}
}
int inv(int x) {
	int res = 1;
	while (x >= N) {
		res = P - 1ll * res * (P / x) % P;
		x = P % x;
	}
	return 1ll * res * v[x] % P;
}