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.

Input and Output 

The program reads sets of data from a text file. Each data set, that describes a puzzle, has the format $w\ h\ n\ m_1\ w_1\ h_1\ \dots\ m_n\ w_n\ h_n$, where $0 < w,h \le 100$ are the dimensions of the surface to be rebuild, $0 < n \le 10$ is the number of groups of similar tiles, m_k is the number of similar tiles in the k-th group and $w_k\ h_k$ are the width and the height of the tiles in the k-th group. Input data are correct, i.e. the tiles can be always combined to rebuild the surface and all tiles must be used in the process.

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.

Sample Input 

3 2 2
2 1 1
2 1 2

5 2 2
2 1 1
4 1 2

Sample Output 

11
56