Nội dung bài toán

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

Hệ số nhị thức ~ \binom{a}{b} ~ được định nghĩa là: ~ \binom{a}{b} = \frac{a!}{b! \cdot (a-b)!}~ với ~ 0 \leq b \leq a ~.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~ n ~: số lượng phép tính.
• ~ n ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~.

Dữ liệu ra

• In ra ~ n ~ số nguyên, mỗi số là giá trị của ~ \binom{a}{b} \mod (10^9 + 7) ~.

Ràng buộc

• ~ 1 \leq n \leq 10^5 ~
• ~ 0 \leq b \leq a \leq 10^6 ~

Ví dụ

Dữ liệu vào

3
5 3
8 1
9 5

Dữ liệu ra

10
8
126

Giải thích:

1. ~ \binom{5}{3} = \frac{5!}{3! \cdot 2!} = \frac{120}{6 \cdot 2} = 10 ~.
2. ~ \binom{8}{1} = \frac{8!}{1! \cdot 7!} = 8 ~.
3. ~ \binom{9}{5} = \frac{9!}{5! \cdot 4!} = 126 ~.