Product Expansion Length

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

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

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.