P5081 Tweetuzki Loves Drawing Balls

This problem is an adaptation that got called out… ~~afraid of getting blasted~~.

Tweetuzki has a bag with $N$ indistinguishable balls. Each time, Tweetuzki randomly draws one ball and then puts it back. Find the expected number of draws needed to have drawn every ball at least once. “Having drawn all balls” means that every ball in the bag has been drawn at least once.

One line with one integer $N$ $(1 \le N \le 10^7)$.

Output one integer on one line, representing the expected number of draws. Since this number may be very large, output it modulo $20040313$ (a prime).

### Sample Explanation 1 Drawing one ball the first time is enough to have drawn all balls. ### Sample Explanation 2 The probability of having drawn all balls in two draws is $\frac{1}{2}$, in three draws is $\frac{1}{4}$, in four draws is $\frac{1}{8}$, …, and in $k$ draws is $\frac{1}{2^{k-1}}$. Therefore: $$E(2) = \frac{2}{2} + \frac{3}{4} + \frac{4}{8} + \frac{5}{16} + \cdots = 3$$ ### Sample Explanation 3 By experiments and calculation, we get: $$E(3) = \frac{11}{2}$$ After taking modulo $20040313$, the answer is $10020162$. ## Constraints For $30\%$ of the testdata, $N \le 5$. For $70\%$ of the testdata, $N \le 10^5$. For $100\%$ of the testdata, $1 \le N \le 10^7$. Translated by ChatGPT 5