Bob đang ở trong cửa hàng với vô số viên bi đầy màu sắc. Cửa hàng có \(k\) màu bi khác nhau và Bob được phép lấy \(n\) viên bi trong số đó. Bob muốn có ít nhất mỗi màu một viên bi.

Bạn hãy giúp Bob tính số cách chọn mà Bob có thể có. Vì kết quả có thể rất lớn nên nên chỉ in ra kết quả sau khi chia lấy dư \((10^9+7).\)

Dữ liệu

• Dòng đầu tiên chứa số nguyên \(T\) \((T \le 200)\) - số lượng testcase.

  Mỗi testcase có dạng như sau:

  • Một dòng ghi 2 số nguyên \(n\), \(k\) \((1 \le k \le n \le 10^6)\). Trong đó \(n\) là số viên bi Bob chọn và \(k\) là số màu khác nhau của các viên bi.

Kết quả

• Gồm \(T\) dòng, mỗi dòng ghi một số nguyên là số cách lấy các viên bi mà Bob có thể có.

Ví dụ