곱셈 전개식의 길이

대수학에서 곱셈식을 전개하는 일은 손이 많이 간다. 자연수 n이 주어졌을 때 다음 곱을 생각하자.

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

n=2, n=3이면 전개식은 다음과 같다.

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

식을 텍스트로 출력하려면 x의 지수와 a의 아래 첨자를 표현해야 하므로, 실제 출력 모양은 세 줄을 사용한다고 생각한다. 맨 위 줄의 숫자는 열 번호를 보여 주기 위한 것이다.

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

따라서 n=3일 때 전개식의 길이는 40이다. n이 커졌을 때 이 길이를 구하라.

출력 모양에는 불필요한 괄호가 없어야 한다. 또한 지수가 1인 x는 x1처럼 쓰지 않고 x로 쓴다.

n=10일 때 전개식의 앞부분은 다음과 같은 모양으로 시작한다.

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

첫째 줄에 자연수 n이 주어진다. (1 <= n <= 1,000,000,000)

전개식을 위와 같은 방식으로 나타냈을 때의 길이를 출력한다. 길이가 매우 커질 수 있으므로 10,000으로 나눈 나머지를 출력한다.