Problem H
No Way? Many Ways!
Languages
en
sv
After a long day of studying at school, Jack is eager to get home. But today, it seems like there are several roadworks in the area where Jack usually walks. These are not just any roadworks; they are special modular equation roadworks taking place between the school and Jack’s house, blocking many of Jack’s original paths home!
"Oh no! What am I going to do now? I have no way to get home now!" Jack thinks. But after a few thoughts, he realizes that there might still be many ways home! Jack lives on an $R \times C$ grid, where the school is located at the top left cell with coordinates $(0,0)$, and Jack’s house is located at the bottom right corner with coordinates $(C-1,R-1)$.
All the cells Jack can be on have integer coordinates $(x,y)$. A modular equation roadwork can be described with a pair of integers $(r_i, m_i)$. $(r_i, m_i)$ means that there is roadwork going on at all cells $(x,y)$ that satisfy the modular equation $x-y=r_i ~ (\text{mod} ~ m_i)$.
When Jack is on a cell $(x,y)$, he can only move to a neighboring cell, i.e., either $(x+1,y)$, $(x,y+1)$, $(x-1,y)$, or $(x,y-1)$. Jack is not allowed to move to a cell where there is roadwork.
Jack always wants to take the shortest path home and wonders how many different paths there are for him to get home now that there are $N$ different modular equation roadworks. Since the number of different paths home can be quite large, he is okay if the answer is given modulo $10^9+7$.
Input
The first line consists of three integers, $R$, $C$ $(2 \leqslant R,C \leqslant 500)$, and $N$ $(0 \leqslant N \leqslant 10^5)$. $R$ and $C$ are the number of rows and columns in the grid, respectively, and $N$ is the number of different modular equation roadworks. Then follow $N$ lines, where the $i$-th line contains two integers, $r_i, m_i$ $(1 \leqslant r_i < m_i \leqslant 10^9)$, the values for the $i$-th modular equation roadwork, as described above.
Output
Print an integer - The number of shortest paths for Jack to get home without stepping on a modular equation roadwork. Print the answer modulo $10^9+7$.
Points
Your solution will be tested on several test case groups. To
get the points for a group, it must pass all the test cases in
the group.
|
Group |
Point value |
Constraints |
|
$1$ |
$6$ |
$N = 0$ |
|
$2$ |
$7$ |
$N = 1$ |
|
$3$ |
$7$ |
$N \leqslant 100$, $R,C \leqslant 100$ |
|
$4$ |
$31$ |
$r_i = 1$, for all $1 \leqslant i \leqslant N$. |
|
$5$ |
$21$ |
$N \leqslant 1000$, $R+C \leqslant m_i$ for all $1 \leqslant i \leqslant N$. |
|
$6$ |
$28$ |
No further constraints. |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 1 2 4 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 9 2 4 9 5 10 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
100 100 1 12 34 |
361294640 |
