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* = 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.