P5081 Tweetuzki 爱取球
题目背景
本题为被指出的改编题……~~害怕被爆破~~
题目描述
Tweetuzki 有一个袋子,袋子中有 $N$ 个无差别的球。Tweetuzki 每次随机取出一个球后放回。求取遍所有球的期望次数。
取遍是指,袋子中所有球都被取出来过至少一次。
输入格式
无
输出格式
无
说明/提示
### 样例解释 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$。