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 The program reads sets of data from a text file. Each data set, that describes a puzzle, has the format whnm1 w1 h1 ... mn wn hn,where0<w,h≤100arethedimensionsofthesurfacetoberebuild, 0 < n ≤ 10 is the number of groups of similar tiles, mk is the number of similar tiles in the k-th group and wk hk 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. Output For each set of data, the program writes the number of tile combinations on a separate line. Note: The first data set in the sample below corresponds to the puzzle shown in figure 1. Sample Input 322 211 212 522 211 412 Sample Output 11 56