#include "inv.h"
#include<bits/stdc++.h>
typedef long long ll;
const int N=1e8+5;
int in[N];
void init(int p){
	in[1]=1;
	for(int i=2;i<=1e8;i++)
		in[i]=(ll)in[p%i]*(p-p/i)%p;
}
int inv(int a){
	return in[a];
}