You have infinite ceramic tiles(磁磚) of some sizes and you want to stick them to fill a rectangle area. What will be the number of all the possible outcome you can make?
For example, if it is a 3-by-2 area, and you have two kinds of tiles: 1-by-2 and 2-by-2, then there are 5 different outcomes you can make:(Let A* be the 1-by-2 tiles and B* be the 2-by-2 tiles)
| A1 | A1 |
| A2 | A2 |
| A3 | A3 |
| A1 | A1 |
| B1 | B1 |
| B1 | B1 |
| B1 | B1 |
| B1 | B1 |
| A1 | A1 |
| A1 | A2 |
| A1 | A2 |
| A3 | A3 |
| A1 | A1 |
| A2 | A3 |
| A2 | A3 |
The first line provides two integers, M and N, which are larger than or equal to 1 and less than 8, indicating the rectangle area that will be filled.
The second line provides an integer, K, that is larger than 1 and less than 5, indicating the amount of types of tiles.
There will be two integers in each of the following K lines, indicating the dimensions of tiles.
The number of all the possible outcome that can be made.
Note that reflection and rotation is NOT considered. That's why the output of the example is 5 instead of 3.