Còn \(10\) ngày nữa là đến kỳ thi HSG tỉnh Quảng Nam, thầy KANGURU muốn chọn ra \(k\) bạn học sinh ưu tú nhất từ \(n\) bạn học sinh trong đội dự tuyển của ITK20 để tham gia thi. Thầy muốn viết một chương trình để tính số cách chọn \({n \choose k}\), nhưng máy tính nhà thầy đang gặp sự cố nên không thể viết được. Vì vậy thầy KANGURU muốn nhờ các bạn học sinh ITK20 viết giúp, ai hoàn thành đầu tiên sẽ được ưu tiên một suất dự thi chính thức cho kỳ thi sắp tới. Các bạn hãy nhanh tay giúp thầy nào!

Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số lượng truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(n\) và \(k\).

Output

• Gồm \(T\) dòng trả lời cho \(T\) truy vấn, mỗi dòng gồm một số nguyên dương duy nhất là số cách chọn học sinh modulo \(10^9+7\).

Ràng buộc

• \(1\leq T\leq10^5\)
• \(0\leq k\leq n\leq10^6\)

Ví dụ

Sample input

3
5 3
8 1
9 5

Sample output

10
8
126