Nhiệm vụ của bạn là tính ~n~ tổ hợp (hệ số nhị thức) dưới modulo ~10^9 + 7~.

Một tổ hợp được tính theo công thức: ~\frac{a!}{b!(a-b)!}~. Giả sử rằng a và b là số nguyên và ~0 \le b \le a~.

Đầu vào:

Dòng đầu tiên chứa một số nguyên ~n~: số lượng phép tính tổ hợp cần thực hiện.

Sau đó là ~n~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~.

Đầu ra:

In ra n dòng, mỗi dòng là kết quả của phép tính rồi mod ~10^9 + 7~

Ràng buộc:

~1 \le n \le 10^5~

~0 \le b \le a \le 10^6~

Ví dụ :

Input:

3
5 3
8 1
9 5

Output:

10
8
126