Mike Sees The Storm (Large)

Time limit1sMemory limit1024 MB

Summary

Sum the K-th power of the maximum prefix value over all balanced +1/-1 walks of length 2N from 0, modulo 1e9+7.

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

Problem

The board initially shows $0$ . Mike repeats one of two operations to build a sequence.

If the number on the board is $a$ , erase it and write $a+1$ .
If the number on the board is $a$ , erase it and write $a-1$ .

The two operations may be performed in any order, but each must be performed exactly $N$ times. Let $A_1, A_2, \cdots, A_{2N}$ be the sequence of numbers written on the board, in order.

For every order in which Mike can perform the operations, take the maximum of the resulting sequence, raise it to the $K$ -th power, and add these values together. Print the sum modulo 1 000 000 007.

Input

The first line contains two integers $N$ and $K$ ( $1 \leq N \leq 1\ 000\ 000$ , $1 \leq K \leq 500\ 000$ ).

Output

Print the sum of the $K$ -th powers of the maximum of each sequence Mike can obtain, modulo 1 000 000 007.

Examples2

Example 1
Input
```
2 2
```
Expected output
```
7
```
Example 2
Input
```
1000000 500000
```
Expected output
```
809476062
```