Time Limit: 1000 MS Memory Limit: 512M


Description

Cxh最喜欢赌狗地精,但是搜了70块都没有搜到地精工程师,因为他(地精工程师)没有解决下面这个问题,快来帮帮cxh吧。

下面是一个数列,已经给出了前三项,相信你可以知道是等差数列还是等比数列。现在给你序列的前三项,这个序列要么是等差序列,要么是等比序列,你能求出第k项的值吗。这个值对200907取模。

Input

输入:第一行一个整数 T,表示有 T 组测试数据。

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

Output

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

Sample Input

2

1 2 3 5

1 2 4 5

Sample Output

5

16