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$$$.
You are given an integer $$$1 \le k \le 5000$$$.
Output the answer modulo $$$10^9+7$$$.
1
2
2
6