Tile Puzzle |

In a puzzle a rectangular surface of width *w* and height *h* is split into a collection
of rectangular tiles. The tiles
with the same dimensions form a similarity group. Solving the puzzle is to rebuild
the surface by using the tiles
from the collection. There can be many solutions. Two solutions are considered different
if the tiles from at least
one similarity group follow different placement patterns in the two solutions.
For example, in the puzzle from
figure 1 there are two groups of two similar tiles each. The tiles can be combined
in eleven different ways to solve the puzzle.

Figure 1: Combining tiles to rebuild a surface

Write a program that for a given puzzle, as described above, computes the total number of different solutions of the puzzle. The puzzle surface and the tiles have integer dimensions.

For each set of data, the program writes the number of tile combinations on a separate line.
The first data set in the sample below corresponds to the puzzle shown in figure 1.

3 2 2 2 1 1 2 1 2 5 2 2 2 1 1 4 1 2

11 56