Nhiệm vụ của bạn là tính toán ~n~ hệ số nhị thức modulo ~10^9 + 7~.

Một hệ số nhị thức ~a \choose b~ có thể được tính bằng công thức ~\frac{a!}{b!(a-b)!}~. Đảm bảo rằng ~a~ và ~b~ là hai số nguyên không âm ~(0 \leq b \leq a)~.

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~ ~-~ số lượng phép tính cần thực hiện.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm ~a~ và ~b~ ~(0 \leq b \leq a \leq 10^6)~.

Output

Gồm ~n~ dòng, mỗi dòng là kết quả của phép tính ~a \choose b~ modulo ~10^9 + 7~.

Sample Input

3
5 3
8 1
9 5

Sample Output

10
8
126