시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 110 20 15 18.072%

문제

대수학에서 전개식을 구하는 것은 꽤나 지루한 작업 중의 하나이다. 자연수 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

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

따라서 우리는 n=3일 때 곱셈 전개식의 길이가 40이 됨을 알 수 있다. 만일 n이 점점 커진다면, 곱셈 전개식의 길이는 어떻게 될까? 이를 구하는 프로그램을 작성하시오.

주의할 점은 출력할 때 불필요한 괄호가 포함되어서는 안 되고, 를 과 같이 표현해서는 안 된다는 것이다.

예를 들어 n=10일 때, 곱셈 전개식의 앞 부분은 아래와 같이 된다.

입력

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

출력

첫째 줄에 식을 전개하였을 때의 길이를 출력한다. 단, 길이가 매우 길어질 수 있으므로 이를 10,000으로 나눈 나머지만을 출력한다.

예제 입력

2

예제 출력

16

힌트

출처

  • 문제를 번역한 사람: author5