Keycards

Time limit1sMemory limit1024 MB

Summary

Count the subsets of the 2N possible keys (a nonempty collection) such that exactly K of the N positions are punched in every chosen key, modulo 1e9+7.

Level: Hard8 of 10
Topics: Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

The room keys in the lodging building of the facility where the JOI spring camp is held have the shape of cards with several holes punched in them. There are N candidate positions where a hole can be punched, and 2N distinct keys were made, each with holes punched in some of these positions.

For the JOI spring camp you received at least 1 and at most 2N keys together. Aligning the candidate hole positions and stacking the keys, you noticed that at exactly K positions, every key you received has a hole punched.

How many sets of received keys make this happen? Find the answer modulo 1 000 000 007 (a prime).

Given N and K, write a program that finds the answer modulo 1 000 000 007.

Input

Read the following input from standard input.

The first line contains the integers N and K separated by a space.

Output

Print one line to standard output giving the number of key sets. On the first line of output, print the answer modulo 1 000 000 007.

Constraints

1 ≤ N ≤ 1 000 000: the number of candidate hole positions
0 ≤ K ≤ N: the number of positions where every received key has a hole punched

Examples4

Example 1
Input
```
3 3
```
Expected output
```
1
```
Example 2
Input
```
3 2
```
Expected output
```
6
```
Example 3
Input
```
3 1
```
Expected output
```
30
```
Example 4
Input
```
3 0
```
Expected output
```
218
```