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

#6630. 跳一跳 加强版

标签: 传统 | 时间限制: 100 ms | 内存限制: 2 MiB |

题目描述

加强自 #6342。

现有一排方块，依次编号为 $1\ldots n$ 。

方块 $1$ 上有一个小人，已知当小人在方块 $i$ 上时，下一秒它会等概率地到方块 $i$（即不动），方块 $i+1$，方块 $i+2$ ……方块 $n$ 上。

求小人到达方块 $n$ 所需要的期望时间（单位：秒）。由于答案可能很大，请输出答案四舍五入到整数之后的结果。

输入格式

一个整数 $n$.

输出格式

一个整数 $ans$

样例 1

输入

1

输出

0

样例 2

输入

1145141919

输出

24547273737

数据范围与提示

对于 30% 的数据，$n\le 10^7$.
对于 50% 的数据，$n\le 2\times 10^9$.
对于 100% 的数据，$n\le 5\times 10^{10}$.