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 file DATA3.txt will contain 5 lines, each containing an integer 0 <= N <= 30, the width of the board you want to tile with dominoes.
The output file OUT3.txt 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).
1 4 3 25 13
1 36 11 952111 413351