P408030 - GYM102964 D Krosh and series sum - SSOJ - 省实信息奥赛评测系统

Memory Limit：256 MB Time Limit：2 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

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

Output

Input

Output

Krosh Kaliningrad Contest 1

408030: GYM102964 D Krosh and series sum

Description

Source/Category

加入题单