Problem Element - Find Binomial Coefficients in Number theory

### Problem Statement:

Given three integers n and k, find \binom{n}{k} = \frac{n!}{k!(n-k)!}. Output the answer modulo 10^9+7

### Approach:

**Precomputation of Factorials and Inverses**:- We precompute the factorials and their modular inverses up to 10^6.
**Factorial**: fac[i] stores i! modulo 10^9+7.**Inverses**: We use Fermat’s Little Theorem to compute the modular inverses of the factorials: a^{−1} ≡ a^{p−2} mod p (p is prime).- This allows us to compute k! and (n−k)! inverses efficiently.

**Binomial Coefficient Calculation**:- The formula for the binomial coefficient is given by: \binom{n}{k} = \frac{n!}{k!(n-k)!}
- Using the precomputed factorials and inverses, we can compute this in constant time: \binom{n}{k} mod p = fac[n] x inv[k] mod p x inv[n-k] mod p

**See this for reference**:- Fermat Binomials in Number theory

### Complexity:

**Time Complexity:**Computing exponentiation will give`O(log n)`

, computing factorial will give`O(N)`

, computing modular inverse factorial will give`O(N+log N)`

. Maximum Time complexity will be`O(N)`

.**Space Complexity:**`O(N)`

. To store the factorials`O(N)`

and inverse`O(N)`

.