题目背景

本题为被指出的改编题……害怕被爆破

题目描述

Tweetuzki 有一个袋子，袋子中有 $N$ 个无差别的球。Tweetuzki 每次随机取出一个球后放回。求取遍所有球的期望次数。

取遍是指，袋子中所有球都被取出来过至少一次。

输入格式

一行一个整数 $N$ $(1 \le N \le 10^7)$。

输出格式

一行一个整数，表示期望次数。由于这个数可能很大，输出对 $20040313$ （是个质数）取模。

1

1

2

3

3

10020162

提示

样例解释 1

第一次取出一个球即可取遍所有球。

样例解释 2

两次就取遍所有球的概率为 $\frac{1}{2}$，三次取遍所有球的概率为 $\frac{1}{4}$，四次取遍所有球的概率为 $\frac{1}{8}$，……，$k$ 次取遍所有球的概率为 $\frac{1}{2^{k-1}}$。故：

$$E(2) = \frac{2}{2} + \frac{3}{4} + \frac{4}{8} + \frac{5}{16} + \cdots = 3 $$

样例解释 3

通过试验及计算可得：

$$E(3) = \frac{11}{2}$$

对 $20040313$ 取模后答案为 $10020162$。

数据范围及约定

对于 $30\%$ 的数据，$N \le 5$。
对于 $70\%$ 的数据，$N \le 10^5$。
对于 $100\%$ 的数据，$1 \le N \le 10^7$。