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 ~1\,000\,000~ (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 ~1\,000\,000~).

Sample Input

1
4
3
25
13

Sample Output

0
11
0
0
0

Problem Resource: DWITE