{"code":"complexity","name":"Phép tính và máy tính","description":"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. \r\n\r\n**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.** \r\n\r\nCó thể coi phòng học có vô hạn máy tính. \r\n\r\nYê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)$.\r\n\r\n

Input

\r\n\r\n-\tDòng đầu tiên là $T$ tương ứng với số truy vấn cần hỏi $(T \\leq 5*10^5)$\r\n-\t$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)$\r\n\r\n

Output

\r\n\r\n- 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$)\r\n\r\n

Scoring

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3\r\n 1 2 23\r\n 2 4 2\r\n 1 4 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 92\r\n 38\r\n 60\r\n ```\r\n \r\n ??? warning \"Note\"","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}