ModInverse

Pre-computation of modular inverses. Assumes LIM ≤ mod and that mod is a prime.

3 lines Works

content/number-theory/ModInverse.h — Simon Lindholm, source: Russian page

const ll mod = 1000000007, LIM = 200000;
ll* inv = new ll[LIM] - 1; inv[1] = 1;
rep(i,2,LIM) inv[i] = mod - (mod / i) * inv[mod % i] % mod;