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
Comments