# Binomial Coefficient

$(mn )=(n−m)!m!n! =1⋅2⋅3⋯kn(n−1)⋯(n−k−1) $

Implementation stolen from: https://cp-algorithms.com/combinatorics/binomial-coefficients.html#improved-implementation

A simple recursive implementation

Another Note: $(mn )=(n−mn )$

Recently, I tried to use this formula for this Codeforces problem https://codeforces.com/contest/1999/submission/277997377, but I ran into integer overflow problems, even after using `long long`

.

They do something like this in the solution https://codeforces.com/blog/entry/132373 (Problem F) This is the tourist solution https://codeforces.com/contest/1999/submission/274741514

Yes, actually, CP algorithms teaches how to tackle this.

### Factorial module $%$ MOD

The modular inverse here