시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 6 6 35.294%

문제

3 × N개의 점이 찍혀있는 직사각형 그리드가 있다. 그리드 상의 모든 점은 최대 8개의 이웃한 점을 가지고 있다.

그리드 상의 점을 연결해서 만들 수 있는 다각형의 개수를 구하려고 한다. 다각형은 아래와 같은 조건을 만족해야 한다.

꼭지점은 3 × N개 모두로 이루어져 있어야 한다.
다각형에서 인접한 꼭지점은 그리드상에서 이웃한 점이어야 한다.
단순 다각형이어야 한다. 즉, 변이 교차하며 안된다.

아래 그림은 N=6인 경우에 가능한 두 가지 다각형이다.

N이 주어졌을 때, 만들 수 있는 다각형의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 양의 정수 N이 주어진다. (N <= 1,000,000,000).

출력

다각형의 만드는 방법의 수를  1,000,000,000로 나눈 나머지를 출력한다.

예제 입력

3

예제 출력

8

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 5번