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