I was aware of using a^(mod2)%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:
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. asked 14 Jul '14, 13:00

There are three common ways of computing modular inverses. They have all been explained here: http://emaxx.ru/algo/reverse_element It's a Russian website, so translate it to English, if needed. answered 26 Jul '14, 18:43

vai ami o kisu bujlam na. onek time pass korlam but still don't know how it works. @forthright