테트리스 2

시간 제한2초메모리 제한256 MB

요약

일자 막대를 제외한 테트로미노 6종을 회전시켜 3×N 직사각형을 빈틈없이 채우는 경우의 수를 1,000,000으로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 행렬
정답자: 아직 제출이 없습니다

문제

테트리스 조각으로 $3 \times N$ 크기의 직사각형을 빈틈없이 덮는 방법이 몇 가지인지 센다.

테트리스 조각은 정사각형 네 개를 변끼리 이어 붙인 도형이고, 모두 일곱 종류이다. 이 문제에서는 정사각형 네 개가 한 줄로 늘어선 $1 \times 4$ 조각을 쓰지 않는다. 남은 여섯 조각은 다음과 같다.

O      T      S      Z      J      L

##     ###    .##    ##.    #..    ..#
##     .#.    ##.    .##    ###    ###

#는 조각이 덮는 칸, .은 빈 칸이다. 조각은 놓기 전에 $90$ 도, $180$ 도, $270$ 도로 돌릴 수 있다. 같은 조각을 몇 번이든 쓸 수 있다. 조각끼리 겹치거나 직사각형 밖으로 나가면 안 된다. 직사각형을 조각으로 나눈 모양이 다르면 서로 다른 방법으로 센다.

입력

첫째 줄에 자연수 $N$ 이 주어진다. ( $1 \le N \le 1\,000\,000$ )

출력

첫째 줄에 $3 \times N$ 직사각형을 덮는 방법의 수를 $1\,000\,000$ 으로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
4
```
예상 출력
```
16
```
예제 2
입력
```
1
```
예상 출력
```
0
```
예제 3
입력
```
8
```
예상 출력
```
388
```