int invans[100000001];
int powp(int a,int b,int p)
{
    int res=1;
    a%=p;
    while(b)
    {
        if(b&1)res=(1LL*res*a)%p;
        a=(1LL*a*a)%p;
        b>>=1;
    }
    return res;
}
void init(int p)
{
    for(int i=1;i<=100000000;i++)
        invans[i]=powp(i,p-2,p); 
}
int inv(int x)
{
    return invans[x];
}