Tweetuzki 爱取球

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

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$。