Informatica Online Judge

  Make Polygon (Large) [0700 / 02BC]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

3xN개의 점으로 이루어진 직사각형 격자를 생각해 보자. 각각의 점은 최대 8개의 이웃한 점을 가지고 있다.



우리는 다음의 조건을 만족하는 다각형을 만들어낼 수 있도록 격자 위의 점을 연결하는 방법의 개수를 알고자 한다.

1. 다각형의 꼭지점들의 집합은 3xN개의 점으로 이루어져 있다.

2. 다각형의 이웃한 꼭지점들은 격자에서 이웃한 점들이어야 한다.

3. 각 다각형의 변은 서로 겹치지 않아야 한다.


N=6일 때 두 가지 가능한 다각형의 예를 보여준다. 물론 이 예 이외에도 많이 존재한다.

주어진 N에 대하여 위의 예와 같이 점을 연결하는 가능한 방법의 수를 1,000,000,000으로 나눈 나머지 값으로 계산하는 프로그램을 작성하시오.

Input

첫 번째 줄에 양의 정수 N이 입력된다.(N<=1,000,000,000)

Output

첫 번째 줄에 가능한 방법의 수를 1,000,000,000으로 나눈 나머지 값을 출력한다.

IO Example

예시1)
입력
3

출력
8

예시2)
입력
4

출력
40

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