[AdditionalFile6342.zip](file://AdditionalFile6342.zip?type=additional_file)

#6342. 跳一跳

标签: 传统 | 时间限制: 1000 ms | 内存限制: 64 MiB |

题目描述

现有一排方块，依次编号为 $1\ldots n$。
方块 $1$ 上有一个小人，已知当小人在方块 $i$ 上时，下一秒它会等概率地到方块 $i$（即不动），方块 $i+1$，方块 $i+2$……方块 $n$ 上。
求小人到达方块 $n$ 所需要的期望时间（单位：秒）。

输入格式

一个数字 $n$。

输出格式

若答案 $ans=\frac{A}{B}$ 输出 $A \times B^{-1} \bmod (10^9+7)$。其中 $B^{-1}$ 表示 $B \bmod (10^9+7)$ 下的逆元。

样例 1

输入

1

输出

0

样例 2

输入

10000000

输出

406018741

数据范围与提示

对于 $50\%$ 的数据，$n \leqslant 10^6$。
对于 $100\%$ 的数据，$1 \leqslant n \leqslant 10^7$。