모듈러 인버스 (modulo inverse)

typedef long long ll;
typedef pair<ll,ll> pii;
pll MInv(ll a, ll b) { // a : inverse n | b : modulo p
    if(!a) return {0,1};
    auto [p,q] = MInv(b%a,a);
    return {q-(b/a)*p,p};
}

v[0]=0, v[1]=1;
for(int i=2; i<=n; ++i) v[i]=v[M%i]*(M-M/i)%M; // v[n] : inverse n | M : modulo p