Cho số nguyên dương $n$ và cho số tự nhiên $k$ nằm trong đoạn $[0,n]$ Hãy tính tổ hợp chập $k$ của $n$

Input

Dòng đầu là số bộ test $t(1\le t\le {10}^5)$

Tiếp theo $t$ dòng mỗi dòng chứa hai số $k$ và $n$ thỏa mãn $(0\le k\le n\le {10}^5)$

Output

Kết quả tổ hợp chập $k$ của $n$ bởi vì kết quả quá lớn chỉ cần lấy phần dư của kết quả chia cho ${10}^9+7$

Ví dụ

Input

4
6 3
10 7
41 21
20 17

Output

20
120
128935337
1140