Informatica Online Judge

  확장 오각형 [0173 / 00AD]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 824   Total Tried : 1034


The Champion of this Problem (C++) : gs18116 - ms / 127byte
My Best Submission (C++) : N/A

[]

Background

오각형을 아래 그림과 같이 확장해 나간다.

아래 그림에서 n번째 나타날 오각형의 점의 수를 구하는 프로그램을 작성하시오.

Input

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

Output

첫째 줄에 n단계에서 점의 개수를 1,000,000,004로 나눈 나머지를 출력한다.

IO Example

입력1
1
출력1
5

입력2
3
출력2
22

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]