Count

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ờ đỏ.

Khi $K=1$, hai người phất cờ xanh liên tiếp là chính người đó: đi hết một vòng tròn từ người đó về lại chính họ phải gặp ít nhất $P$ người phất cờ đỏ, tức là $n-1\ge P$. Khi $K=0$, cấu hình mọi người cùng phất cờ đỏ là cấu hình chiến thắng duy nhất.

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: 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$.

Dữ liệu vào

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)$.

Dữ liệu ra

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$.

Ràng buộc

• $1\le q\le {10}^5$
• $1\le L\le R\le {10}^6$
• $0\le K,P\le {10}^6$

Subtasks

• Subtask 1 ($40\%$ số điểm): $q=1$, $1\le L,R\le 20$.
• Subtask 2 ($30\%$ số điểm): $q=1$, $L=R$.
• Subtask 3 ($20\%$ số điểm): $q=1$.
• Subtask 4 ($10\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ