Hôm nay, ShyWoou đượ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, ... \)

ShyWoou 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, ShyWoou đà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 ≤ 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 ≤ 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.

Sample Input

2
5 6 7
1 2 3

Sample Output

196
10

Giải thích

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

Giới hạn

• \(30\)% số tests đầu tiên có \(a, d, n ≤ 10^3\).

• \(30\)% số tests tiếp theo có \(a, d, n ≤ 10^6\).

• \(40\)% số tests còn lại không ràng buộc gì thêm.