Problem Statement
    
Time limit: 5 seconds.
 
You have an R times C rectangle divided into unit squares.
 
You want to perform a sequence of two actions.
The first action is to remove some collection of individual unit squares. (All remaining squares are left in their original positions.
The second action is to perfectly tile all the remaining squares using horizontally and/or vertically placed 1x2 dominoes.
 
Consider all possible ways of correctly performing these two actions. Among them, count all possible ways to perform the first action. Return that count modulo 1,000,000,007.
Definition
    
Class:
CountTilings
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int R, int C)
(be sure your method is public)
Limits
    
Time limit (s):
5.000
Memory limit (MB):
256
Stack limit (MB):
256
Notes
-
In a perfect tiling of a collection of squares each 1x2 domino tile covers two squares, and each square is covered by exactly one domino.
Constraints
-
R will be between 1 and 8, inclusive.
-
If R = 8, C will be between 1 and 200, inclusive.
-
If R = 7, C will be between 1 and 1,000, inclusive.
-
If R <= 6, C will be between 1 and 8,000, inclusive.
Examples
0)

    
1
1
Returns: 1
As your first action you must remove the only square.
For your second action you are then left with an empty set of squares, and that can be perfectly tiled using an empty set of dominoes.
1)

    
2
3
Returns: 18
There are 18 valid ways to perform the first action. All of them are shown below, using 'x' for a square you remove and '.' for a square you keep.

  xxx
  xxx

  xx.  x.x  .xx  ..x  x..  xxx  xxx
  xx.  x.x  .xx  xxx  xxx  ..x  x..

  ..x  .x.  x..  x..  ..x  xx.  .xx  ...  ...
  ..x  .x.  x..  ..x  x..  ...  ...  xx.  .xx

  ...
  ...


Note that for some of these there are multiple valid ways to perform the second action. That has no impact on our answer, each of the options shown above is only counted once.
2)

    
1
50
Returns: 365010934
For a 1xC strip we are essentially just tiling it with 1x1 and 1x2 tiles. The numbers of such tilings are clearly Fibonacci numbers.
The exact number of tilings for C = 50 is F[51] = 20,365,011,074.
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.