Trung cần xây dựng một hàng rào có độ dài ~m~.

Tổ tiên Trung truyền lại cho cậu một thanh gỗ có độ dài vô tận để xây hàng rào. Cậu sẽ chặt thanh gỗ này thành ~m~ thanh gỗ ngắn hơn với độ rộng như nhau và độ cao là một số nguyên dương không lớn hơn ~n~.

Gọi ~h_i~ là độ cao của thanh gỗ ở vị trí ~i~, Trung cần xây dựng một hàng rào đẹp thỏa mãn các tính chất sau:

• ~h_1~ có thể nhận một giá trị bất kì.

• Nếu ~2 \cdot h_i > n~, ~h_{i+1}~ có thể nhận giá trị bất kì.

• Nếu ~2 \cdot h_i \le n~, ~h_{i+1} \ge 2 \cdot h_i~.

• ~2 \cdot h_m > n~.

Giúp Trung tính số lượng hàng rào đẹp có thể xây dựng, chia lấy dư cho ~10^9+7~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~T~ (~1\le T \le 10^5~) - số test cases cần xử lý.

• ~T~ dòng tiếp theo mỗi dòng gồm hai số nguyên dương ~n, m~ là độ cao tối đa và số thanh gỗ cần để xây dựng hàng rào.

Tổng ~n~ trong ~T~ test cases không vượt quá ~10^5~.

Tổng ~m~ trong ~T~ test cases không vượt quá ~5\times 10^5~.

Output

• Gồm ~T~ dòng, mỗi dòng là kết quả của một test case.

Subtask

Subtask ~1~ (~20~ điểm): ~n,m\le 300~.

Subtask ~2~ (~30~ điểm): ~n,m\le 3000~.

Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

5
1 2
2 2
3 4
5 6
10 10

Sample Output 1

1
2
44
4629
564985327