시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3831198130.337%

문제

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

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

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

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

매번 곱셈 전개식을 구하는 번거로움을 덜기 위해, 당신은 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를 x1과 같이 표현해서는 안 된다는 것이다.

예를 들어 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으로 나눈 나머지만을 출력한다.

예제 입력 1

2

예제 출력 1

16

예제 입력 2

3

예제 출력 2

40

예제 입력 3

8

예제 출력 3

2332

출처

  • 문제를 번역한 사람: author5
  • 문제의 오타를 찾은 사람: wider93