D. Krosh and series sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh has a homework: calculate the sum of the following series: $$$\sum\limits_{n = 1}^{\infty} \frac{n^k}{2^n}$$$, where $$$k$$$ is given. Help him to calculate it. It's guaranteed that the answer is integer. Output it modulo $$$10^9+7$$$.

Input

You are given an integer $$$1 \le k \le 5000$$$.

Output

Output the answer modulo $$$10^9+7$$$.

Examples
Input
1
Output
2
Input
2
Output
6