## Summary

Given a modular `MOD`

, if we want to calculate the division of two integers, we could use the technique Modular Multiplicative Inverse.

`a / b = a * b_ % MOD => b * b_ % mod = 1`

To calculate `b_`

, we could use Fermat’s little theorem. If* *`mod`

is a prime number, we have

`b^mod % mod = b => b^(mod-1) % mod = 1 => b^(mod-1) = b * b_ => b_ = b^(mod-2) % mod`

If we use Binary Exponentiation technique, we could calculate `b_`

efficiently.

```
auto b_ = power(b, mod - 2, mod);
ll power(ll base, int i, int mod) {
if (i == 0) {
return 1;
} else if (i == 1) {
return base;
} else if ((i & 1) == 0) {
return power((base * base) % mod, i / 2, mod);
} else {
return (base * power((base * base) % mod, (i - 1) / 2, mod)) % mod;
}
}
```