1026: Dominos Tiling
[Creator : ]
Description
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.
Input
The input will contain 5 lines, each containing an integer 0≤N≤30, the width of the board you want to tile with dominoes.
Output
The output will contain 5 lines, where each line represents the number of ways to tile a 3×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×N board with dominoes by 1000000).
Sample Input Copy
1
4
3
25
13
Sample Output Copy
0
11
0
0
0