I was aware of using **a^(mod-2)%mod** and **extended euclidean** for finding modular inverse. But today, while solving CNTWAYS, I came across another method for finding modular inverse. The previous two methods were too slow and apparently this method is much faster.

This is what I found in the Tester’s solution:

```
/* calculate all inverses of 1..8000000 mod MOD */
inv[1] = 1;
REP(i,2,800010) inv[i] = MOD - ((MOD/i)*inv[MOD%i]%MOD);
```

I found it interesting. So anybody has any idea how this code is actually working. Exactly what is this? I have never seen it before.