점 연결하기

3 x N개의 점이 찍힌 직사각형 격자가 있다. 격자의 각 점은 주변에 있는 최대 8개의 이웃한 점과 연결될 수 있다.

격자 위의 점들을 연결해 만들 수 있는 다각형의 개수를 구하려고 한다. 다각형은 다음 조건을 모두 만족해야 한다.

1. 3 x N개의 모든 점이 꼭짓점으로 사용되어야 한다.
2. 다각형에서 서로 인접한 두 꼭짓점은 격자에서도 이웃한 점이어야 한다.
3. 단순 다각형이어야 한다. 즉, 변끼리 교차해서는 안 된다.

아래 그림은 N = 6일 때 만들 수 있는 다각형 두 가지를 보여 준다.

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

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

만들 수 있는 다각형의 수를 1,000,000,000으로 나눈 나머지를 출력한다.