Sau khi mua quá nhiều sách, Loli muốn chia sẻ lại niềm vui đọc sách đến đám bạn của hắn. Hãy giúp Loli tính nhanh số cách chia ~n~ quyển sách cho ~k~ người bạn (tất nhiên có thể có người không nhận được sách, tuy nhiên cần đảm bảo quyển sách nào cũng được chia).

Hai cách chia được coi là khác nhau nếu tồn tại ~i~ sao cho người thứ ~i~ nhận được số sách khác nhau ở trong 2 cách chia. Bạn chỉ cần in ra phần dư khi chia cho ~10^9+7~.

Input:

Lấy từ tệp DIVBOOK.INP:

• Dòng đầu tiên chứa số nguyên ~q\ (q\le100)~ là số truy vấn cần tính.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~n,k\ (1\le n,k\le10^7)~.

Output:

Ghi ra tệp DIVBOOK.OUT:

• Gồm ~q~ dòng, mỗi dòng chứa phần dư của số cách chia khi chia cho ~10^9+7~.

Sample Input 1

1
3 2

Sample Output 1

4

Giải thích

Có ~4~ cách chia tất cả:

• Người 1 có ~0~ quyển sách, người 2 có ~3~ quyển.
• Người 1 có ~1~ quyển sách, người 2 có ~2~ quyển.
• Người 1 có ~2~ quyển sách, người 2 có ~1~ quyển.
• Người 1 có ~3~ quyển sách, người 2 có ~0~ quyển.

Ràng buộc

• 30% số test có ~n,k\le20~.
• 30% số test có ~n,k\le10^3~.
• 40% số test không có ràng buộc gì thêm.