Problem G
Lestir

Þú komst heil/l á húfi til Vilníus og vilt heimsækja ýmsar borgir í Litháen.

Borgirnar eru staðsettar eftir beinni línu og eru númeraðar frá $1$ til $N$. Vilníus er númeruð $1$.

Í hverri borg er lestarstöð. Í lestarstöð $i$-tu borgarinnar getur þú aðeins stigið um borð í þær lestir sem leggja af stað þaðan. Þessi lest mun stoppa í $d_i$-tu hverri borg og ferðaáætlun hennar samanstendur af $x_i$ stoppum, þar sem við teljum ekki upphafsstöðina. Ef $d_i=0$ er lestin sem ætti að leggja af stað frá $i$-tu borginni biluð, svo þú getur ekki nýtt þá lest.

Nánar tiltekið, ef þú ferð um borð í lestina í $i$-tu borginni þá getur þú farið út úr lestinni í borg númer $i+t\cdot d_i$ fyrir öll $1\le t\le x_i$. Athugaðu að þar sem þú vilt aðeins heimsækja borgir í Litháen munt þú ekki fara lengra en í $N$-tu borgina, jafnvel þó lestin hafi fleiri stopp á ferðaáætlun sinni.

Verkefni

Þú vilt heimsækja einhverjar borgir, mögulega með því að taka lest milli þeirra. Nú veltir þú fyrir þér hvað eru margar ólíkar runur borga sem þú gætir heimsótt ef þú byrjar í Vilníus.

Reiknaðu þessa tölu og prentaðu hana mátað við ${10}^9+7$. Í öðrum orðum, skaltu reikna töluna, deila með ${10}^9+7$ og taka afganginn af deilingunni til að fá töluna sem skal skrifa út.

Inntak

Á fyrstu línu inntaks er ein heiltala $N$, fjöldi borga.

Næst fylgja $N$ línur. $i$-ta þeirra inniheldur tvær heiltölur $d_i$ og $x_i$, gildin sem gefa ferðaáætlun lestarinnar sem leggur af stað frá $i$-tu borginni.

Úttak

Prentið eina heiltölu, fjöldi leiða sem þú getur heimsótt eitthvað hlutmengi $N$ borganna, mátað við ${10}^9+7$.

Takmarkanir

• $1\le N\le {10}^5$

• $0\le d_i\le {10}^9$ (fyrir sérhvert $1\le i\le N$)

• $0\le x_i\le {10}^9$ (fyrir sérhvert $1\le i\le N$)

Hlutverkefni

Sýnidæmi

Það eru $7$ ferðalög koma til greina:

• $1$

• $1\to 2$

• $1\to 2\to 4$

• $1\to 3$

• $1\to 3\to 4$

• $1\to 3\to 5$

• $1\to 4$

5
1 3
2 1
1 3
0 10
3 5

7