#6342. 跳一跳

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WDLGZH2017

题目描述

现有一排方块,依次编号为 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

样例输出 1

0

样例输入 2

10000000

样例输出 2

406018741

数据范围与提示

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