Background

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

Problem Description

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.

Input Format

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

Output Format

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).

1

1

2

3

3

10020162

Hint

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