On a N * M grid, a rat starts from (1, 1) and wants to get to the cheese at (N, M). The rat can only move in two directions: right (+1, 0) and up (0, +1).
Moreover, there's K warpholes on the grid, a warphole is an one-way tunnel connecting two points. If the rat moves into the entrance of a warphole, it will be forced to enter the warphole and transported to the corresponding exit.
Your task is to calculate the number of different ways from (1, 1) to (N, M).
For example, let N=2, M=3, K=1, and the only warphole connects (1, 2) and (2, 3).
There's two paths from (1, 1) to (2, 3):
(1, 1) -> (1, 2) -> (2, 3) and (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) .
(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) is illegal, because you have to enter the warphole at (1, 2).
The input consists of multiple test cases. For each test case, the first line contains three integers N, M, K. Followed by K lines of the form Ai Bi Ci Di, where (Ai, Bi), (Ci, Di) are the coordinates of the entrance and exit of i-th warphole.
1 < N, M < 105, 0 < K < 1000.
For all 1 < i, j < K, input guarantees Ai < Ci, Bi < Di, (Ai,Bi) != (Ci,Di),
(Ai,Bi) != (Aj,Bj).
There's no warphole entrances at (1, 1).
For each testcase, output the answer modulo 1,000,000,007.
4 4 1 2 2 3 3 1 4 1 1 2 1 3 5 5 2 2 2 3 4 3 3 5 3 100000 100000 1 2 2 99999 99999 1 1 0
12 1 26 615667476 1
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|