题目描述

现在你有一个函数：

inline int f(int x) {
    int tot = 0, alr = 0, now;
    while (alr<x) {
        now = rand(x) + 1;
        tot++;
        if (!v[now]) alr++, v[now] = 1;
    }
    return tot;
}

其中 $v$ 可以被看成是一个无限大的每一个位置初始值都为 $0$ 的数组，$\mathrm{rand}(x)$ 等概率均匀随机返回 $[0,x)$ 中的一个整数。

对于一个给定的 $n$，大(shen)葱想知道 $f(n)$ 的期望是多少。

但是这个问题太简单了，于是他把它丢给了你。

输入格式

一行一个整数 $N$。

输出格式

一行一个数，表示 $f(N)$ 的期望，精确到整数。

样例

input

10

output

29

数据范围与提示

对于 $20\%$ 的数据，$N\le 100$；

对于 $40\%$ 的数据，$N\le 10^3$；

对于 $60\%$ 的数据，$N\le 3\times 10^5$；

对于 $80\%$ 的数据，$N\le 10^7$；

对于 $100\%$ 的数据，$N\le 10^9$。