테트리스

테트리스 조각으로 $3 \times N$ 크기의 직사각형을 빈칸 없이 채우려고 한다.

사용할 수 있는 조각은 정사각형, T자, S자, Z자, L자, J자 모양의 여섯 가지 테트로미노이다. 각 조각은 필요한 만큼 사용할 수 있으며, $90^\circ$, $180^\circ$, $270^\circ$ 회전해서 놓을 수 있다. 일자형 $1 \times 4$ 조각은 사용하지 않는다.

조각은 격자에 맞춰 놓아야 하며 서로 겹치거나 직사각형 밖으로 나가면 안 된다. 가능한 배치의 수를 구하라.

첫째 줄에 자연수 $N$이 주어진다. $N$은 $300$보다 작거나 같다.

테트리스 조각으로 $3 \times N$ 크기의 직사각형을 채우는 경우의 수를 $1{,}000{,}000$으로 나눈 나머지를 출력한다.