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.

Yêu cầu: 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~, 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~.