题目描述

加强自 #6342。

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

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

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

输入格式

一个整数 $n$.

输出格式

一个整数 $ans$

1

0

1145141919

24547273737

数据范围与提示

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