[r]

Jaher is a brilliant algorithmist, but he is also a bit absent minded. For example, he has some difficulties making things fit into his suitcase. Can you help him?

For simplicity, let us assume a two-dimensional suitcase a × b, where n rectangular objects must fit. Objects can be placed at any position within the suitcase, without overlap, but they can not be rotated. In how many ways can we put the objects?

Input

Input consists of several cases. Each case begins with a, b and n. Follow n pairs of strictly positive natural numbers, which indicate the sizes of the objects. The area of the objects exactly covers the suitcase, and there is always at least one possible solution. (The first case in the sample input corresponds to the picture.)

Output

[r]

For every suitcase, print a line with its number and how many possible solutions exist.

Public test cases

**Input**

4 5 6 1 5 3 1 1 1 1 4 2 3 1 1 2 3 2 2 2 2 1 1 1 1 1 1 1 5 3 1 1 1 2 1 2 6 8 10 3 4 1 6 2 3 1 1 2 2 1 4 2 1 2 5 1 2 1 1

**Output**

#1: 32 #2: 2 #3: 1 #4: 6 #5: 4384

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++