Tetris 2

Time limit2sMemory limit256 MB

Summary

Count the ways to tile a 3 by N rectangle with the six tetrominoes except the straight piece, modulo 1,000,000.

Level: Medium7 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples3

Example 1
Input
```
4
```
Expected output
```
16
```
Example 2
Input
```
1
```
Expected output
```
0
```
Example 3
Input
```
8
```
Expected output
```
388
```