Combinations (nCr mod p) - Classic Problems | Repovive

CLS31. Combinations (nCr mod p)

1s256 MB

Given non-negative integers $n$ and $r$ , compute the binomial coefficient $C(n, r)$ modulo $10^9 + 7$ .

The binomial coefficient is defined as: $C(n, r) = \frac{n!}{r! \cdot (n-r)!}$

$n \quad r$

$C(n, r) \mod (10^9 + 7)$

Input

5 2

Explanation

For this input, the required output is 10.

Output

Input

10 0

Explanation

For this input, the required output is 1.

Output

Input

10 10

Explanation

For this input, the required output is 1.

Output

Given non-negative integers $n$ and $r$ , compute the binomial coefficient $C(n, r)$ modulo $10^9 + 7$ .

The binomial coefficient is defined as: $C(n, r) = \frac{n!}{r! \cdot (n-r)!}$

$n \quad r$

$C(n, r) \mod (10^9 + 7)$