Lập trình tính tổ hợp không lặp chập ~k~ từ ~n~ phần tử. Do dữ liệu lớn nên kết quả cần modulo cho ~10^9+7~.

Input

• Dòng đầu tiên chứa số nguyên ~T~ là số testcase.
• ~T~ dòng tiếp theo chứa hai số nguyên ~n~ và ~k~.

Output

• In ra kết quả cần tính ứng với mỗi testcase. Mỗi testcase in trên một dòng.

Constraints

• ~1 \leq T \leq 10^5~.
• ~0 \leq k \leq n \leq 10^6~.

Samples

Sample Input 1

3
5 3
8 1
9 5

Sample Output 1

10
8
126