F. Krosh and series sum 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh has given a new math homework: find the sum of the following series: $$$\sum\limits_{n = 1}^{\infty} \frac{(C_n^k) ^ 2}{2^n}$$$, where $$$k$$$ is given. Help him to find it for given $$$k$$$. It's guaranteed that answer is integer. Print it modulo prime number $$$10^9+7$$$.

Input

You are given integer $$$0 \le k \le 10^6$$$.

Output

Print the series sum modulo $$$10^9+7$$$.

Example
Input
2
Output
26
Note

$$$C_n^k$$$ – number of ways to choose $$$k$$$ objects from $$$n$$$ objects.