#include "inv.h"
#define F(i,l,r) for (int i=l;i<=r;++i)
constexpr int N=1e8+5;
int Inv[N];
void init(int p){
    Inv[1]=1;
    F(i,2,N-1) Inv[i]=(p-p/i)*Inv[p%i]%p;
    return ;
}
int inv(int x){
    return Inv[x];
}