题目描述

现有一排方块，依次编号为 1, 2, ..., n。

方块 1 上有一个小人，其移动规则如下：当小人在方块 i 上时，下一秒会等概率移动到方块 i（即不动）、方块 i+1、方块 i+2、……、方块 n 中的任意一个。

请计算小人从方块 1 出发，到达方块 n 所需要的期望时间（单位：秒）。

输入格式

• 输入仅包含一个整数 n，表示方块的总数。

输出格式

• 设答案为分数形式 ans = A/B（A、B 为互质正整数），输出 A × B⁻¹ mod (10⁹+7) 的结果。
• 其中 B⁻¹ 表示 B 在模 10⁹+7 意义下的乘法逆元。

样例输入 1

1

样例输出 1

0

样例输入 2

10000000

样例输出 2

406018741

数据范围与提示

• 对于 50% 的数据，1 ≤ n ≤ 10⁶；
• 对于 100% 的数据，1 ≤ n ≤ 10⁷。