Description

给你一个序列的前3项，要么等差数列要么等比序列，你能求出第k项的值吗。如果过大对200907取模

Input Format

输入T 组测试数据

每组测试数据有abc k

Output Format

输出第k项

Sample

样例输入

2
1 2 3 5
1 2 4 5

样例输出

5 
16

Hint

1=<t<=100

1=<a<=b<=c<=10^9

0<k<=10^9