#include "inv.h"

const int N = 1e8;
int mod;
int inv_list[N + 7];

void init(int p){
	mod = p;
	inv_list[0] = inv_list[1] = 1;
	for (register int i = 2; i <= N; i++){
		inv_list[i] = mod - 1ll * (mod / i) * inv_list[mod % i] % mod;
	}
}

int inv(int x){
	if (x <= N) return inv_list[x];
	return mod - 1ll * (mod / x) * inv(mod % x) % mod;
}