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

【题意】

已知一个序列（ 等差 或 等比 序列）的前 $3$ 项 $a_1,a_2,a_3$，求出第 $k$ 项的值 $a_k$，对 200907 取模。

【输入格式】

第一行一个整数 $T$（$1 \le T \le 100$），表示有 $T$ 组测试数据。

每组测试数据一行四个整数 $a_1,a_2,a_3,k$（$1 \le a_1 \le a_2 \le a_3 \le 10^9,1 \le k \le 10^9$）。

【输出格式】

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

【样例输入】

2
1 2 3 5
1 2 4 5

【样例输出】

5
16

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