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

2
5 6 7
1 2 3

196
10