마스코트

JOI는 친구와 마스코트를 가지고 놀았다. 즐거운 시간은 순식간에 지나갔고, 친구가 돌아간 지금은 뒷정리를 할 시간이다.

JOI는 마스코트를 R × C개 가지고 있고, 정리에는 세로 R행, 가로 C열의 격자가 늘어선 직사각형 영역을 사용한다. 한 칸에는 마스코트 하나가 놓인다. 위에서 A번째 행, 왼쪽에서 B번째 열의 칸을 (A, B)라고 표현하기로 하자. 정리가 시작되는 단계에서 이미 N개의 마스코트가 놓여 있다. 정리를 시작할 때 마스코트가 놓여 있지 않은 칸이 적어도 하나 있다.

JOI는 마스코트를 하나씩 놓아 정리한다. 새로 마스코트를 하나 놓았을 때, 마스코트가 있는 칸 전체가 하나의 직사각형이 되면 JOI는 조금 행복해진다(처음 상태에서 마스코트가 있는 칸 전체가 하나의 직사각형이었던 경우는 제외한다). 마스코트가 있는 칸 전체가 하나의 직사각형이 된다는 것은, 어떤 네 정수 r1, r2, c1, c2 (1 ≤ r1 ≤ r2 ≤ R이고 1 ≤ c1 ≤ c2 ≤ C)가 존재하여 r1 ≤ i ≤ r2이고 c1 ≤ j ≤ c2인 모든 칸 (i, j)에 마스코트가 있고, 그 밖의 다른 어떤 칸에도 마스코트가 없는 것을 말한다. 조금 행복해지는 횟수가 많을수록 JOI는 오늘 밤 푹 잠들 수 있다.

마스코트를 놓을 때, 놓는 마스코트의 종류는 구별하지 않는다. 조금 행복해지는 횟수가 최대가 되는 놓는 방법은 모두 몇 가지인가?

마스코트를 정리하는 장소와 이미 놓여 있는 마스코트의 정보가 주어지면, 조금 행복해지는 횟수가 최대가 되는 마스코트 놓기 방법의 개수를 1 000 000 007로 나눈 나머지를 구하는 프로그램을 작성하라.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 정수 R, C가 공백을 구분으로 쓰여 있다. R은 마스코트를 놓는 장소의 행 수를, C는 마스코트를 놓는 장소의 열 수를 나타낸다.
• 2번째 줄에는 정수 N이 쓰여 있다. N은 정리가 시작되는 단계에서 이미 놓여 있는 마스코트의 개수를 나타낸다.
• 이어지는 N개의 줄에는 처음부터 놓여 있는 마스코트의 정보가 쓰여 있다. 이 줄의 i번째 줄에는 정수 Ai, Bi가 공백을 구분으로 쓰여 있다. 이는 칸 (Ai, Bi)에 처음부터 마스코트가 놓여 있음을 나타낸다. 이 숫자 쌍은 중복되지 않는다.

표준 출력에, 가능한 놓기 방법의 개수를 1 000 000 007로 나눈 나머지를 출력하라.

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