Nguyễn Đình Hải là một thợ xây khét tiếng ở vùng Cao Bằng. Một hôm, ông quyết đinh xây \(n\) tòa tháp để tặng Nguyễn Ngọc Hòa. Hai người này vốn là bạn thân với nhau nhưng do có một số mâu thuẫn đã làm tan nát tình bạn đẹp đẽ này, Hải đã nhận ra lỗi sai của mình nên quyết định xây tháp để tặng Hòa.

• Cách xây tháp :
• Tháp đầu tiên có độ cao là \(a\).
• Kể từ tháp thứ \(2\) trở đi, độ cao của tháp gấp \(2\) lần tháp liền trước và cộng thêm \(b\).

Hãy giúp Hải tính toán xem tháp thứ \(n\) có độ cao bao nhiêu.

• Yêu cầu : Hãy tính xem tháp thứ \(n\) có độ cao là bao nhiêu. Vì kết quả có thể rất lớn nên ghi ra phần chia lấy dữ của kết quả cho \(10^9 + 7\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(T ( T \le 10 )\) là số lần thử nghiệm xây tháp.
• \(T\) dòng tiếp theo là \(3\) số nguyên dương \(a, b, n\).

Output

• Gồm \(T\) dòng, dòng thứ \(k\) là kết quả của lần thử nghiệm thứ \(k\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(a,b,n \le 10^5\).
• Subtask \(2\) (\(20\%\) số điểm): \(a,b,n \le 10^{12}\).
• Subtask \(3\) (\(20\%\) số điểm): \(a,b,n \le 10^{100000}\).

Example

3
1 2 3
3 2 1
1 1 2

10
3
3