17747번 - Mascots 서브태스크다국어

JOI ちゃんは友達とマスコットで遊んでいた．楽しかった時間はあっという間に過ぎ去り，友達が帰った 今は後片付けの時間である．

JOI ちゃんはマスコットを R × C 個持っていて，片付けには縦 R 行，横 C 列のマスが並んだ長方形の領 域を使う．1 個のマスには，1 個のマスコットが置かれる．上から A 行目，左から B 列目のマスのことを (A, B) と表現することにする．片付けが始まる段階で既に N 個のマスコットが置かれている．片付けを始 めるときに少なくとも 1 個はマスコットが置かれていないマスがある．

JOI ちゃんはマスコットを 1 個ずつ置いて片付けをする．新しくマスコットを 1 個置いたときに，マス コットのあるマス全体が 1 個の長方形となれば，JOI ちゃんは少し幸せになる（最初の状態でマスコット のあるマス全体が 1 個の長方形になっていた場合を除く）．マスコットのあるマス全体が 1 個の長方形と なるとは，ある 4 つの整数 r₁, r₂, c₁, c₂ (1 ≤ r₁ ≤ r₂ ≤ R かつ 1 ≤ c₁ ≤ c₂ ≤ C) が存在して，r₁ ≤ i ≤ r₂ かつ c₁ ≤ j ≤ c₂ を満たすどのマス (i, j) にもマスコットがあり，さらに他のいずれのマスにもマスコットがない ことをいう．少し幸せになる回数が多ければ多いほど JOI ちゃんは今晩ぐっすり眠ることができる．

マスコットを置く際，置くマスコットの種類は区別しないものとする．少し幸せになる回数が最大とな るような置き方は全部で何通りあるだろうか．

マスコットを片付ける場所と既に置かれているマスコットの情報が与えられると，少し幸せになる回数が 最大となるようなマスコットの置き方の個数を 1 000 000 007 で割った余りを求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• 1 行目には整数 R,C が空白を区切りとして書かれている．R はマスコットを置く場所の行数を，C は マスコットを置く場所の列数を表す．
• 2 行目には整数 N が書かれている．N は片付けが始まる段階で既に置かれているマスコットの個数 を表す．
• 続く N 行には，最初から置かれているマスコットの情報が書かれている．これらの行の i 行目には 整数 A_i, B_i が空白を区切りとして書かれている．これはマス (A_i, B_i) に最初からマスコットが置かれ ていることを表す．これらの数字の組は重複しない．

標準出力に，考えられる置き方の個数を 1 000 000 007 で割った余りを出力せよ．

• 2 ≤ R ≤ 3 000．
• 2 ≤ C ≤ 3 000．
• 1 ≤ N ≤ 100 000．

• R ≤ 3．
• C ≤ 3．

• R ≤ 50．
• C ≤ 50．

追加の制限はない．