Slalom

Time limit2sMemory limit512 MB

Summary

Count the right-or-up paths from (1, 1) to (n, m) that avoid rectangular obstacles, where each obstacle is passed on either side, modulo 10^9 + 7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Sorting
Solved: No attempts yet

Problem

Little girl Masha likes winter sports, and today she plans to take part in slalom skiing.

The track is a grid of $n \times m$ squares. Rectangular obstacles on the track are made of grid squares. Masha must get from square $(1, 1)$ to square $(n, m)$ . She can move from a square to an adjacent square, either to the right or upward. She cannot enter a square that is occupied by an obstacle.

Each obstacle can be passed in two ways: either it is to the right of Masha's path, or it is to the left. Masha wants to try every way to do this, so she wants to know how many ways there are to pass the track. Two ways are different if some obstacle is to the right of the path in one way and to the left of the path in the other.

Help Masha count the ways to pass the track. The count can be large, so print it modulo $10^9 + 7$ .

The pictures below show the different ways to pass the track in the sample tests.

Input

The first line contains three positive integers $n$ , $m$ , and $k$ ( $3 \le n, m \le 10^6$ , $0 \le k \le 10^5$ ), the size of the track and the number of obstacles.

Each of the next $k$ lines contains four positive integers $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$ ), the coordinates of the bottom left and top right squares of an obstacle.

Squares $(1, 1)$ and $(n, m)$ have no obstacles. No two obstacles overlap, but they may touch.

Output

Print one integer, the number of ways to pass the track modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
3 3 0
```
Expected output
```
1
```
Example 2
Input
```
4 5 1
2 2 3 4
```
Expected output
```
2
```
Example 3
Input
```
5 5 3
2 2 2 3
4 2 5 2
4 4 4 4
```
Expected output
```
3
```