# Modular Inverse

## Problem

Given a formular which result is normally very large, can’t be stored in any primitive data type. Calculate the result in mod $1e9+7$. The formular often involve *division*.
For example, let’s calculate this

## Naive approach

### Naive approach 1 (Heavy Implementation)

- Calculate $n!$, using big number class to store result
- Calculate $(n-r)!r!$, also using a custom implemented
`BigNumber`

class- You can optimize this by calculate $n!/r!$ in one loop. This way you decimate alot of computation

- Divide 2 numbers to get the result
- Mod the result by $1e9+7$

This requires **non-trivial** effort to implement `BigNumber`

class.
`Python`

folks are in luck but most programming language doesn’t support big number by default.
Assume that you are an average programmer like me. You often fail to come up with a correct implementation of the `BigNumber`

class.

### Naive approach 2 (Wrong Answer)

- Calculate $n! \pmod {1e9+7}$
- Calculate $(n-r)!r! \pmod {1e9+7}$
- Same as before. You can optimize this by calculate $n!/r!$ in one loop. This way you decimate alot of computation

- Divide 2 numbers to get the result

This gives WA because the algorithm is wrong mathematically.

## Solution

The problem with naive approach #2 is that, in step 3 where we normally divide 2 numbers, we get incorrect answer.
Because *division* doesn’t work in modular arithmetic, only *multiplication*.
But luckily there is a formular to address this issue,
it converts division to multiplication by leveraging Modular multiplicative inverse.

Formally, **if $k$ is a prime number**, we have

Everytime you were to do *division*, you multiply it with the power $k-2$ of the divisor instead and it’s guaranteed correct mathematically 😎

There is a new problem araise, calculation of $b^{k-2}$ could be expensive (for example $k=1e9+7$). This could easily be solved by using a fast $O(logn)$ power calculation algorithm

```
#define INF (1e9+7)
long long fastPow(int x, int p) {
if(p == 0) return 1;
if(p == 1) return x;
auto k = fastPow(x,p/2);
return k*k*fastPow(x,p%2)%INF;
}
```