Sau khi sửa máy tính xong, giờ học lại được tiếp tục. Và thế là các học sinh phải thực hiện những phép tính trên máy tính của mình. Thế nhưng, thật thiếu công bằng khi mỗi máy tính có khả năng tính toán khác nhau.

Máy tính có số hiệu \(a\) có thể thực hiện \(1 + 2 + ... + (a - 1) + a\) phép tính/giây.

Có thể coi phòng học có vô hạn máy tính.

Yêu cầu : Với mỗi truy vấn \([L, R]\), gọi \(f(a)\) là tổng số phép tính/giây của máy có số hiệu \(a\) trong \(K\) giây. Hãy tính \(f(L) + f(L+1) + ... + f(R)\).

Input

• Dòng đầu tiên là \(T\) tương ứng với số truy vấn cần hỏi \((T \leq 5*10^5)\)
• \(T\) dòng tiếp theo, mỗi dòng là \(3\) số nguyên dương \(L, R, K\) tương ứng với truy vấn và thời gian cần hỏi và (\(L, R, K \leq 10^{18}, L \leq R)\)

Output

• In ra \(T\) dòng tương ứng với câu trả lời cho \(T\) truy vấn (Vì số có thể rất lớn nên hãy in kết quả modulo \(10^9+7\))

Scoring

• \(K <= 10^{18}\)
• Subtask \(1\) (\(20\%\) số điểm): \(T = 1; \ L, R \leq 10^5\)
• Subtask \(2\) (\(20\%\) số điểm): \(T = 1; \ L,R \leq 10^{18}, R - L \leq 10^5\)
• Subtask \(3\) (\(20\%\) số điểm): \(T \leq 5*10^5; \ L, R \leq 10^{18}, R - L \leq 10\)
• Subtask \(4\) (\(20\%\) số điểm): \(T = 1; \ L,R \leq 10^{18}\)
• Subtask \(5\) (\(20\%\) số điểm): \(T \leq 5*10^5; \ L, R \leq 10^{18}\)

Example

3
1 2 23
2 4 2
1 4 3

92
38
60