Tetris

You want to fill a $3 \times N$ rectangle completely with Tetris pieces.

The available pieces are the six tetrominoes shaped like a square, T, S, Z, L, and J. You may use each piece as many times as needed, and each piece may be rotated by $90^\circ$, $180^\circ$, or $270^\circ$. The straight $1 \times 4$ tetromino is not used.

Pieces must be placed on the grid, must not overlap, and must not extend outside the rectangle. Count the number of possible tilings.

The first line contains a positive integer $N$. $N$ is at most $300$.

Print the number of ways to fill the $3 \times N$ rectangle with the pieces, modulo $1{,}000{,}000$.