1908번 - 곱셈 전개식

문제

대수학에서 전개식을 구하는 것은 꽤나 지루한 작업 중의 하나이다. 자연수 n이 주어지면, 아래와 같은 곱셈식을 생각해 볼 수 있다.

(x+a₁)(x+a₂)...(x+a_n-1)(x+a_n)

예를 들어 n=2와 n=3인 경우, 위 식을 전개해 보면 아래와 같은 결과가 된다.

• n=2: x²+x(a₁+a₂)+a₁a₂
• n=3: x³+x²(a₁+a₂+a₃)+x(a₁a₂+a₁a₃+a₂a₃)+a₁a₂a₃

매번 곱셈 전개식을 구하는 번거로움을 덜기 위해, 당신은 n이 주어지면 이를 계산해 주는 프로그램을 작성하려고 한다. 하지만 텍스트로 수식을 출력하려면 위 첨자와 아래 첨자 때문에 아래와 같이 세 줄에 걸쳐서 출력해야 한다. (맨 위의 숫자가 적힌 줄은 길이를 나타내 주기 위함이다.)

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이 점점 커진다면, 곱셈 전개식의 길이는 어떻게 될까? 이를 구하는 프로그램을 작성하시오.

주의할 점은 출력할 때 불필요한 괄호가 포함되어서는 안 되고, x를 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으로 나눈 나머지만을 출력한다.

제한

힌트