테트리스 2

테트리스 조각으로 $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$으로 나눈 나머지를 출력한다.