Binomial Coefficient 3

Time limit1sMemory limit256 MB

Summary

Compute the binomial coefficient C(N, K) modulo 1,000,000,007 for N up to 4,000,000.

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

Problem

You are given a natural number $N$ and an integer $K$ . Write a program that computes the remainder of the binomial coefficient $\binom{N}{K}$ divided by 1,000,000,007.

Input

The first line contains $N$ and $K$ , separated by a single space. ( $1 \le N \le 4{,}000{,}000$ , $0 \le K \le N$ )

Output

Print the remainder of $\binom{N}{K}$ divided by 1,000,000,007 on the first line.

Examples5

Example 1
Input
```
5 2
```
Expected output
```
10
```
Example 2
Input
```
1 0
```
Expected output
```
1
```
Example 3
Input
```
1 1
```
Expected output
```
1
```
Example 4
Input
```
2 1
```
Expected output
```
2
```
Example 5
Input
```
50 25
```
Expected output
```
605552882
```