题目描述

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

输入格式

第一行一个整数$\red{ T}$，表示有$\red{ T}$ 组测试数据；

对于每组测试数据，输入前三项$\red{a,b,c}$，然后输入$\red{ k}$。

输出格式

对于每组数据输出第$\red{ k }$项的值，对$\red{ 200907 }$取模。

样例

输入样例

2
1 2 3 5
1 2 4 5

输出样例

5
16

第一组是等差序列，第二组是等比数列。

数据范围与提示

对于全部数据，$\red{ 1\le T\le 100}$, $\red{1\le a\le b\le c\le 109}$， $\red{1\le k\le109}$, $\red{1≤T≤100}$, $\red{1≤a≤b≤c≤109}$, $\red{1≤k≤109}$。