题目描述
BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你序列的前三项 $a_1, a_2, a_3$，这个序列要么是等差序列，要么是等比序列，你能求出第 $k$ 项的值吗？
如果第 $k$ 项的值太大，输出对 $200907$ 取模后的结果即可。
输入格式
第一行包含一个整数 $T$，表示有 $T$ 组测试数据；
每组测试数据占一行，包含四个整数 $a_1, a_2, a_3, k$.
- $1 \le T \le 10000$
- $1 \le a_1 \le a_2 \le a_3 \le 10^5$
- $1 \le k \le 10^9$
输出格式
对于每组数据，在一行内输出第 $k$ 项的值 $a_k$，结果对 $200907$ 取模。
样例输入 #1
2
1 2 3 5
1 2 4 5