Tuấn đang chuẩn bị một trò chơi cho chương trình truyền hình như sau: Có một số người chơi được chọn và ngồi thành vòng tròn. Mỗi người có ~2~ lá cờ: một cờ xanh và một cờ đỏ. Khi có hiệu lệnh, tất cả mọi người sẽ đồng loạt phất lên đúng một lá cờ.

Một cấu hình được coi là chiến thắng nếu:

• Có đúng ~K~ người phất lá cờ màu xanh.

• Giữa hai người phất cờ xanh liên tiếp trong vòng tròn có ít nhất ~P~ người phất cờ đỏ.

Số người chơi có thể nằm trong khoảng từ ~L~ đến ~R~. Ban sản xuất muốn biết đối với mỗi trường hợp ~(L, R, K, P)~ có bao nhiêu cách chiến thắng, tính trên tất cả số người chơi ~n~ thỏa mãn ~L \le n \le R~, hai cách được coi là khác nhau nếu tồn tại một người phất lên cờ có màu khác.

Cho ~q~ câu hỏi, mỗi câu hỏi gồm bốn số nguyên ~L, R, K, P~. Với mỗi câu hỏi, hãy tính tổng số cấu hình chiến thắng xét trên tất cả ~n~ thỏa mãn ~L \le n \le R~.

Vì số lượng cấu hình có thể rất lớn, hãy in ra kết quả lấy dư với ~10^9+7~.

Input

Dòng đầu tiên ghi số nguyên ~q~ ~(1 \le q \le 10^5)~ — số lượng câu hỏi. Mỗi câu hỏi gồm ~4~ số ~L, R, K, P~ ~(1 \le L \le R \le 10^6, 0 \le K, P \le 10^6)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ in ra một số nguyên — số cách chiến thắng ứng với tình huống thứ ~i~, lấy dư theo mod ~10^9+7~.

Scoring

Sample Input 1

2
6 6 3 1
10 20 4 2

Sample Output 1

2
2277

Notes

Trong câu hỏi có ~6~ người chơi, ~3~ người phất cờ xanh và có ít nhất ~1~ cờ đỏ giữa mỗi người, có ~2~ cấu hình thỏa mãn với những người phất cờ xanh:

• Cấu hình ~1~: ~1, 3, 5~

• Cấu hình ~2~: ~2, 4, 6~