DWITE Online Computer Programming Contest, December 2010, Problem 3

Counting the number of tilings of different sized boards with dominoes (i.e. $2$ by $1$ rectangles) can be a pretty difficult task. However, here you must only determine the number of ways to tile boards of height $3$ and some width.

The input will contain 5 lines, each containing an integer $0\le N\le 30$, the width of the board you want to tile with dominoes.

The output will contain 5 lines, where each line represents the number of ways to tile a $3\times N$ board with dominoes modulo $1000000$ (i.e. The output is the remainder you get when you divide the number of ways to tile a $3\times N$ board with dominoes by $1000000$).

Sample Input

1
4
3
25
13

Sample Output

0
11
0
0
0

Problem Resource: DWITE