Problem Description

Tweetuzki has a bag containing \( N \) indistinguishable balls. Each time, Tweetuzki randomly draws one ball and then puts it back. Calculate the expected number of draws required to draw all the balls at least once.

Drawing all the balls means that every ball in the bag has been drawn at least once.

Input Format

A single line containing an integer \( N \) \((1 \le N \le 10^7)\).

Output Format

A single line containing an integer representing the expected number of draws, modulo \( 20040313 \) (a prime number).

Sample Input and Output

Sample Input #1

1

Sample Output #1

1

Sample Input #2

2

Sample Output #2

3

Sample Input #3

3

Sample Output #3

10020162

Notes

Sample Explanation #1

Drawing one ball is sufficient to draw all the balls.

Sample Explanation #2

The probability of drawing all balls in two draws is \( \frac{1}{2} \), in three draws is \( \frac{1}{4} \), in four draws is \( \frac{1}{8} \), ..., 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

Through experimentation and calculation:

\[ E(3) = \frac{11}{2} \]

After taking modulo \( 20040313 \), the answer is \( 10020162 \).

Data Range and Constraints

For \( 30\% \) of the data, \( N \le 5 \).
For \( 70\% \) of the data, \( N \le 10^5 \).
For \( 100\% \) of the data, \( 1 \le N \le 10^7 \).

见题面 Input 部分

见题面 Output 部分