Một lớp học có ~n~ học sinh. Thầy giáo muốn chọn đúng ~k~ học sinh lên bảng kiểm tra bài cũ.

Hai cách chọn được gọi là khác nhau nếu tồn tại ít nhất một học sinh được chọn trong cách thứ nhất nhưng không được chọn trong cách thứ hai.

Do số lượng cách chọn có thể rất lớn, hãy cho biết số dư của số cách chọn khi chia cho:

~1000000007 = 10^9 + 7~

Ví dụ, với ~n = 5~ học sinh ~A, B, C, D, E~ và ~k = 3~, có 10 cách chọn:

~ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE~

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~T~, là số lượng bộ test.

• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~n~ và ~k~.

Ràng buộc

• ~1 ≤ T ≤ 10^5~.
• ~1 ≤ k ≤ n ≤ 1000~.

Kết quả

Với mỗi bộ test, in ra trên một dòng số cách chọn đúng ~k~ học sinh từ ~n~ học sinh, lấy dư theo ~10^9 + 7~.

Ví dụ

Dữ liệu vào

2
5 3
6 2

Kết quả

10
15

Giải thích

• Với ~n = 5~, ~k = 3~:

  ~C(5,3) = 10~

• Với ~n = 6~, ~k = 2~:

  ~C(6,2) = 15~