Tiling Dominoes

Given a rectangular grid, with dimensions m × n, compute the number of ways of completely tiling it with dominoes. Note that if the rotation of one tiling matches another, they still count as different ones. A domino is a shape formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares. An example of a tiling is shown below. Input The input will consist of a set of lines with m n, given the restriction n ∗ m < 101. Output For each line of input, output the number of tilings in a separate line. Sample Input 2 10 4 10 88 Sample Output 89 18061 12988816