408030: GYM102964 D Krosh and series sum

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

D. Krosh and series sumtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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$$$.

ExamplesInput
1
Output
2
Input
2
Output
6

Source/Category

加入题单

上一题 下一题 算法标签：