Tetris 2

Count the ways to cover a $3 \times N$ rectangle completely with tetris pieces.

A tetris piece is four unit squares joined edge to edge, and there are seven of them. This problem does not use the $1 \times 4$ piece whose four squares sit in a single line. The remaining six pieces are:

O      T      S      Z      J      L

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

A # is a square the piece covers and a . is empty. You can rotate a piece by $90$, $180$, or $270$ degrees before placing it. You can use the same piece any number of times. Pieces must not overlap and must not stick out of the rectangle. Two coverings are different when the rectangle is split into pieces differently.

The first line contains a natural number $N$ ($1 \le N \le 1\,000\,000$).

Print the number of ways to cover the $3 \times N$ rectangle, modulo $1\,000\,000$.