Combination

Interview

Time limit1sMemory limit256 MB

Summary

Compute N choose R modulo 1,000,000,007 for 0 ≤ R ≤ N ≤ 1,000,000 using a prime modulus.

Level: Medium4 of 10
Topics: Math, Number theory, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

In an introductory statistics class, Junha was given an assignment to count the number of shortest paths from the bottom-left corner to the top-right corner of a grid $a$ wide and $b$ tall.

As you know, the answer is $\binom{a+b}{b}$ . Just looking at it makes you excited to compute a combination, right? It turns out that computing combinations can be done with code too. Let's solve the assignment with code!

Input

The first line gives $N$ and $R$ . ( $0 \le R \le N \le 1{,}000{,}000$ )

Output

Print the value of $\binom{N}{R}$ modulo $1{,}000{,}000{,}007$ . ( $1{,}000{,}000{,}007$ is prime)

Examples2

Example 1
Input
```
4 2
```
Expected output
```
6
```
Example 2
Input
```
30 15
```
Expected output
```
155117520
```