Description

huhe在学等差数列和等比数列,当已知前三项时，就可以知道是等差数列还是等比数列，在给你序列的前三项,这个序列要么是等差序列,要么是等比序列,你能求出第k项的值吗。如第k项的值太大，对其取模 200907。

Format

Input

输入 T,表示有T组测试数据。 对于每组测试数据,输人前三项 a,b,c,然后输入 k

Output

对于每组数据,输出第k项取模 200907 的值

Samples

2
1 2 3 5
1 2 4 5

5
16

Sample Description

第一组是等差序列,第二组是等比数列

Data scale

1≤T<100. 1<a<b<c<10^9 0<k<10^9