Counting Matrices with Local Minima

You are given an n×m matrix filled with all the integers from $1$ to $n\times m$ exactly once. In this matrix, a cell is said to be a local minimum if its value is strictly less than the values in all of its neighboring cells. Two cells are considered neighbors if they share either a common edge or a common vertex (i.e. up to eight neighbors).

You are also given the complete set of positions of the local minima in the matrix. Your task is to determine how many matrices (i.e. assignments of the numbers) exist such that the set of local minima is exactly as given.

The answer should be output modulo $12,345,678$.

Note: The positions are 1-indexed. It is guaranteed that the input list includes all the local minima in the matrix.

inputFormat

The input consists of:

• The first line contains two integers n and m, representing the number of rows and columns of the matrix.
• The second line contains an integer k, the number of local minimum cells.
• Each of the following k lines contains two integers r and c (1-indexed), representing the row and column indices of a local minimum cell.

outputFormat

Output a single integer, which is the number of valid matrices modulo $12,345,678$.

sample

2 2
1
1 1

6