#include<bits/stdc++.h>
#include "inv.h"
using namespace std;
int iv[100000010];
void init(int p){
	iv[1] = 1;
	for(int i = 2; i <= 100000000; i++) iv[i] = (long long)(p - p / i) * iv[p % i] % p;
}
int inv(int x){
	return iv[x];
}