Mascots
Time limit2sMemory limit256 MB
Count the orders of placing the remaining mascots so that the number of steps where the occupied cells form a full rectangle is maximized, modulo 1e9+7.
- Level
Hard8 of 10
- Topics
- Combinatorics, Dynamic programming, Math, Implementation
- Solved
- No attempts yet
Problem
JOI was playing with mascots together with a friend. The fun time passed in the blink of an eye, and now that the friend has gone home, it is time to clean up.
JOI has R × C mascots, and for cleaning up she uses a rectangular area of cells arranged in R rows and C columns. One cell holds one mascot. The cell in the A-th row from the top and the B-th column from the left is denoted (A, B). When cleaning up begins, N mascots are already placed. When cleaning up begins, there is at least one cell with no mascot.
JOI cleans up by placing the mascots one at a time. When she places one new mascot, if the set of all cells containing a mascot forms a single rectangle, JOI becomes a little happy (except for the case where the set of all cells containing a mascot already formed a single rectangle in the initial state). The set of all cells containing a mascot forms a single rectangle means that there exist four integers r1, r2, c1, c2 (1 ≤ r1 ≤ r2 ≤ R and 1 ≤ c1 ≤ c2 ≤ C) such that every cell (i, j) with r1 ≤ i ≤ r2 and c1 ≤ j ≤ c2 contains a mascot, and no other cell contains a mascot. The more times JOI becomes a little happy, the better she sleeps tonight.
When placing mascots, the kinds of mascots are not distinguished. How many ways are there to place the mascots such that the number of times she becomes a little happy is maximum?
Given the area for cleaning up the mascots and the information on the mascots already placed, write a program to find the number of ways to place the mascots that maximizes the number of times she becomes a little happy, modulo 1 000 000 007.
Input
Read the following input from standard input.
- The first line contains the integers R, C separated by a space. R is the number of rows of the area for placing mascots, and C is the number of columns of the area for placing mascots.
- The second line contains the integer N. N is the number of mascots already placed when cleaning up begins.
- The following N lines contain information on the mascots placed from the start. The i-th of these lines contains the integers Ai, Bi separated by a space. This means that a mascot is placed at cell (Ai, Bi) from the start. These pairs of numbers are distinct.
Output
Print the number of possible ways to place the mascots modulo 1 000 000 007 to standard output.
Constraints
- 2 ≤ R ≤ 3 000.
- 2 ≤ C ≤ 3 000.
- 1 ≤ N ≤ 100 000.