题目描述

根据等差数列和等比数列的性质，当已知前三项时，就可以知道是等差数列还是等比数列。

现在给出序列的前三项，这个序列要么是等差序列，要么是等比序列（如果是等比数列，比值是整数），你能求出第 $k$ 项的值吗。

如果第 $k$ 项的值太大，对 $200907$ 取模。

输入

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

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

输出

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

样例

2
1 2 3 5
1 2 4 5

5
16

说明

【样例解释】

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

【数据范围与提示】

对于全部数据， $1≤T≤100$,$1≤a≤b≤c≤10$^$9$,$1≤k≤10$^$9$。