Annettuna on n binomikerrointa, ja tehtäväsi on laskea ne modulo 10^9+7.

Binomikerroin {a \choose b} lasketaan kaavalla \frac{a!}{b!(a-b)!}. Binomikerroin on määritelty, kun a ja b ovat kokonaislukuja ja 0 \le b \le a.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: laskujen määrä.

Sitten syötteessä on n riviä, joista jokainen sisältää kaksi kokonaislukua a ja b.

Tuloste

Tulosta jokaista lukuparia vastaava binomikerroin modulo 10^9+7.

Rajat

• 1 \le n \le 10^5
• 0 \le b \le a \le 10^6

Esimerkki

Syöte:

3
5 3
8 1
9 5

Tuloste:

10
8
126