슬라롬

시간 제한2초메모리 제한512 MB

요약

직사각형 장애물이 있는 격자에서 (1, 1)부터 (n, m)까지 오른쪽이나 위로만 가는 경로를 세웁니다. 각 장애물을 왼쪽과 오른쪽 중 어느 쪽으로 지나는지로 구분하고, 그 개수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 정렬
정답자: 아직 제출이 없습니다

문제

어린 소녀 마샤는 겨울 스포츠를 좋아하고, 오늘은 슬라롬 스키 경기에 출전할 계획이다.

코스는 $n \times m$ 칸의 격자로 이루어져 있다. 코스에는 격자 칸으로 구성된 직사각형 장애물이 있다. 마샤는 $(1, 1)$ 칸에서 $(n, m)$ 칸까지 가야 한다. 마샤는 인접한 칸으로 오른쪽 또는 위쪽으로만 이동할 수 있다. 장애물이 있는 칸으로는 이동할 수 없다.

각 장애물은 두 가지 방법으로 통과할 수 있다. 장애물이 마샤의 경로 오른쪽에 있거나 왼쪽에 있는 경우다. 마샤는 가능한 방법을 모두 시도해 보고 싶어 하므로, 코스를 통과하는 방법이 몇 가지인지 알고 싶어 한다. 어떤 장애물이 한 방법에서는 경로의 오른쪽에 있고 다른 방법에서는 왼쪽에 있다면, 두 방법은 서로 다르다.

마샤가 코스를 통과하는 방법의 수를 구하도록 도와라. 방법의 수가 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 구한다.

아래 그림은 예제 테스트에서 코스를 통과하는 서로 다른 방법을 보여준다.

입력

첫 줄에 양의 정수 $n$ , $m$ , $k$ 가 주어진다 ( $3 \le n, m \le 10^6$ , $0 \le k \le 10^5$ ). 각각 코스의 크기와 장애물의 개수이다.

다음 $k$ 개 줄에는 각각 양의 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 주어진다 ( $1 \le x_1 \le x_2 \le n$ , $1 \le y_1 \le y_2 \le m$ ). 장애물의 왼쪽 아래 칸과 오른쪽 위 칸의 좌표이다.

$(1, 1)$ 칸과 $(n, m)$ 칸에는 장애물이 없다. 장애물끼리는 겹치지 않지만 맞닿을 수는 있다.

출력

코스를 통과하는 방법의 수를 $10^9 + 7$ 로 나눈 나머지를 한 줄에 출력한다.

예제3

예제 1
입력
```
3 3 0
```
예상 출력
```
1
```
예제 2
입력
```
4 5 1
2 2 3 4
```
예상 출력
```
2
```
예제 3
입력
```
5 5 3
2 2 2 3
4 2 5 2
4 4 4 4
```
예상 출력
```
3
```