Problem H
No way? Many ways!
Languages
en
sv
Efter en lång dag av studier i skolan längtar Jack att ta sig hem. Men just idag verkar det som att det är flera vägarbeten på gång på i området där Jack brukar gå. Men det är inte vilka vägarbeten som helst, utan det är speciella modulär-ekvations-vägarbeten som pågår mellan skolan och Jacks hus, vilket blockerar många av Jacks ursprungliga vägar att ta sig hem på!
“Oh nej! Vad ska göra jag göra nu? Jag har ju inga vägar hem nu!” tänker Jack. Men ett antal tankar senare insåg han att det möjligtvis ändå finns många vägar hem! Eftersom Jack nämligen på ett rutnät av storlek $R \times C$, där skolan ligger vid rutan som ligger längst upp till vänster, med koordinaterna $(0,0)$, och Jacks hus ligger vid hörnet längst ner till höger med koordinaterna $(C-1,R-1)$.
Alla rutor man kan befinna sig på har heltalskoordinater $(x,y)$. Ett modulär-ekvations-vägarbetn kan beskrivas med ett par heltal $(r_i,m_i)$. $(r_i,m_i)$ innebär då att det är vägarbete som pågår på alla rutor $(x,y)$ som uppfyller modulär ekvationen $x-y=r_i ~ (\text{mod} ~ m_i)$.
När man befinner sig på en ruta $(x,y)$, kan Jack endast röra sig till någon närliggande ruta, alltså antingen $(x+1,y), (x,y+1), (x-1,y),$ eller $(x,y-1)$. Jack får inte gå på en ruta där det pågår vägarbete.
Jack vill alltid ta den kortaste vägen hem, och undrar hur många olika vägar det finns för honom att ta sig hem nu när det pågår $N$ olika modulär-ekvations-vägarbete. Eftersom antalet olika vägar att ta sig hem kan bli ganska stort, så är han okej ifall svaret är givet modulo $10^9+7$.
Indata
Första raden består av tre heltal, $R$, $C$ $(2 \leqslant R,C \leqslant 500)$, och $N$ $(0 \leqslant N \leqslant 10^5)$. $R$ och $C$ är antalet rader respektive kolumner i rutnätet, och $N$ är antalet olika modulär-ekvations-vägarbeten. Därefter följer $N$ rader, där den $i$:te raden innehåller två heltal, $r_i, m_i$ $(1 \leqslant r_i < m_i \leqslant 10^9)$, värdena för det $i$:te modulär-ekvations-vägarbetet, som beskrivits ovan.
Utdata
Skriv ut ett heltal - Antalet kortaste vägar för Jack att ta sig hem utan att gå på ett modulär-ekvations-vägarbete. Skriv svaret modulo $10^9+7$.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$6$ |
$N = 0$ |
|
$2$ |
$7$ |
$N = 1$ |
|
$3$ |
$7$ |
$N \leqslant 100$, $R,C \leqslant 100$ |
|
$4$ |
$31$ |
$r_i = 1$, för alla $1 \leqslant i \leqslant N$. |
|
$5$ |
$21$ |
$N \leqslant 1000$, $R+C \leqslant m_i$ för alla $1 \leqslant i \leqslant N$. |
|
$6$ |
$28$ |
Inga ytterligare begränsningar. |
| 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 |
