Tính toán đơn giản

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hôm nay, BichSonNhat được thầy Hùng giao cho bài tập Tin vô cùng đơn giản, đó chính là tính tổng dãy số sau : \(1, 3, 5, 7, 9, ...\)

BichSonNhat nhận thấy rằng đây là dãy Cấp số cộng quen thuộc cộng sai \(d = 2\) nên áp dụng công thức vào giải rất đơn giản.

Thấy thế, thầy Hùng đành nâng cao mức độ khó của bài toán, thầy biến đổi dãy số trên thành dãy:

\((a), (a + d), (a + 1 + 2*d), (a + 3 + 3*d), (a + 6 + 4*d), (a + 10 + 5 * d), ...\)

Để cho dễ thấy, với \(a = 5, d = 6\) thầy cho trước một dãy số sau đây: \(5, 11, 18, 26, 35, 45, 56, ...\)

Với \(a, d\) là những số cho trước, hãy tính \(n\) số liên tiếp trong dãy đặc biệt trên.

Vì kết quả có thể rất lớn, nên thầy chỉ yêu cầu các bạn in ra số dư của đáp án cho \(10^9 + 7\).

Cảm nhận được độ khó của bài toán, BichSonNhat đành nhờ các bạn hỗ trợ, hãy giúp anh ấy nhé!

Input

Dòng đâu tiên chứa số nguyên dương \(T\) \((T \le 10)\) - là số câu hỏi.

\(T\) dòng, mỗi dòng chứa \(3\) số nguyên dương \(a, d, n\) \((a,d,n \le 10^9).\)

Output

Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(a, d, n \le 10^3\).

  • Subtask \(2\) (\(30\%\) số điểm): \(a, d, n \le 10^6\).

  • Subtask \(3\) (\(40\%\) số điểm): không ràng buộc gì thêm.

Example

Test 1

Input
2
5 6 7
1 2 3
Output
196
10
Note

Trong TestCase 1, tổng dãy số \(5 + 11 + 18 + 26 + 35 + 45 + 56 = 196\)

Trong TestCase 2, tổng dãy số \(1 + 3 + 6 = 10\)


Bình luận