Product Expansion Length

Time limit2sMemory limit128 MB

Summary

Compute, modulo 10000, the exact printed character length of the fully expanded symbolic expansion of the product (x+a1)...(x+an) for n up to 1e9.

Level: Hard8 of 10
Topics: Math, Combinatorics, Number theory
Solved: No attempts yet

Problem

Expanding products in algebra can take a lot of work. Given a natural number n, consider the following product.

(x+a1)(x+a2)...(x+an-1)(x+an)

For n=2 and n=3, the expanded forms are as follows.

n=2: x^2+x(a1+a2)+a1a2
n=3: x^3+x^2(a1+a2+a3)+x(a1a2+a1a3+a2a3)+a1a2a3

To write the expression as text, the exponent of x and the subscripts of a must occupy their own columns, so view the printed expression as three lines. The top line of digits below is only a column ruler.

1234567890123456789012345678901234567890
 3  2
x +x (a +a +a )+x(a a +a a +a a )+a a a
       1  2  3     1 2  1 3  2 3   1 2 3

Therefore, when n=3, the length of the expanded expression is 40. Compute this length for the given n.

The printed form must not contain unnecessary parentheses. Also, x to the first power is written as x, not as x1.

When n=10, the beginning of the expanded expression has this shape.

123456789012345678901234567890123456789012345678
 10  9                                  8
x  +x (a +a +a +a +a +a +a +a +a +a  )+x (a a +
        1  2  3  4  5  6  7  8  9  10      1 2

Input

The first line contains a natural number n. (1 <= n <= 1,000,000,000)

Output

Print the length of the expression when it is written in the form described above. Since the length can be very large, print only its remainder modulo 10,000.

Examples3

Example 1
Input
```
2
```
Expected output
```
16
```
Example 2
Input
```
3
```
Expected output
```
40
```
Example 3
Input
```
8
```
Expected output
```
2332
```