Xiao F and Xiao H are playing a game. Today, they are playing on an $N \times M$ grid. Xiao H wants to test Xiao F's mathematical ability, but Xiao F is not naturally good at math, so he wants your help. To increase the difficulty, Xiao H adds $P$ rectangular obstacles to the grid. Each rectangular obstacle is represented by $U, D, L, R$, meaning all cells from row $U$ to row $D$ and from column $L$ to column $R$ become obstacles. Xiao H guarantees that all rectangular obstacles are disjoint, and that all non-obstacle cells can reach each other directly or indirectly. If two non-obstacle cells share a common edge, they are directly reachable and the distance between them is $1$.

In each game, Xiao F chooses a non-obstacle cell $X$, and Xiao H chooses another non-obstacle cell $Y$. The score of this game is the shortest path distance between $X$ and $Y$. Xiao F needs to calculate the sum of scores for all possible games, modulo $1,000,000,007$. Note that two games are considered the same if the two chosen cells are the same, i.e., $XY$ is equivalent to $YX$.

Input

Read from standard input.

The first line contains three integers $N$ ($1 \le N \le 1,000,000,000$), $M$ ($1 \le M \le 1,000,000,000$), and $P$ ($0 \le P \le 100,000$).

The next $P$ lines each contain four positive integers $U_i, D_i, L_i, R_i$ ($1 < U_i \le D_i < N$, $1 < L_i \le R_i < M$), representing the $i$-th rectangular obstacle. For any two distinct rectangular obstacles $i$ and $j$, they satisfy $D_i + 1 < U_j$ or $D_j + 1 < U_i$, and $R_i + 1 < L_j$ or $R_j + 1 < L_i$.

Output

Output to standard output.

A single line containing one integer, which is the sum of scores of all games modulo $1,000,000,007$.

Examples

Input 1

3 3 1
2 2 2 2

Output 1

64

Note 1

There are 8 pairs with distance 1. There are 8 pairs with distance 2. There are 8 pairs with distance 3. There are 4 pairs with distance 4. The total score is 64.