该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一天，fcg回到了家。

「 Pia!(ｏ ‵-′)ノ”(ノ﹏<。) 」

一本作业砸到了fcg的脸上

「快帮我写作业！！！」

「╰(艹皿艹 )」

「fcg一脸愤怒接下作业本」

已知前三项，求等差数列，等比数列的第k个项。现在xxs的作业本给你序列的前三项，这个数列要么是等比数列，要么是等差数列。

fcg觉得这题过于简单，于是扔给了你。请你帮fcg编一程序，求出数列第k项的值。

输入格式

第一行输入一个整数T；

接下来T行输入四个整数A、B、C、K，每个整数用空格分隔；

输出格式

输出仅一行。 输出一个整数，表示答案对$200907$取模的结果

样例输入

3
1 2 3 6
5 6 7 9
4 16 64 7

样例输出

6
13
16384

数据的规模与约定

$T\in[1,100]$

$A,B,C,K\in[1,10^9]$