1615：【例 1】序列的第 k 个数

题目描述

BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 $k$ 项的值吗？如果第 $k$ 项的值太大，对 $200907$ 取模。

输入格式

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

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

输出格式

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

样例

样例输入 #1

2
1 2 3 5
1 2 4 5

样例输出 #1

5
16

样例解释 #1

第一组数据：

• 前三项：$1, 2, 3$，公差为 $1$，是等差数列。
• 第 $5$ 项：$1 + (5-1) \times 1 = 5$，输出 $5$。

第二组数据：

• 前三项：$1, 2, 4$，公比为 $2$，是等比数列。
• 第 $5$ 项：$1 \times 2^{5-1} = 1 \times 16 = 16$，输出 $16$。

数据范围

对于全部数据：

• $1 \le T \le 100$
• $1 \le a \le b \le c \le 10^9$
• $1 \le k \le 10^9$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要判断序列是等差数列还是等比数列。判断方法：

• 如果 $b - a = c - b$，则为等差数列，公差 $d = b - a$，第 $k$ 项为 $a + (k-1) \times d$。
• 否则为等比数列，公比 $q = b / a$（注意 $a, b, c$ 是整数，且保证 $q$ 为整数？题目说序列要么等差要么等比，且 $a, b, c$ 是整数，但公比可能是分数？实际上，等比数列的前三项为整数且公比可能是分数，但题目保证公比为整数？样例中公比是整数。但为了严谨，应该检查 $b^2 = a \times c$ 是否成立，如果成立则为等比数列，公比 $q = b / a$（需要整数除法）。

对于等比数列，第 $k$ 项为 $a \times q^{k-1}$，需要快速幂取模。注意取模数 $200907$ 不是质数，但 $a$ 和 $q$ 可能与模数不互质，但因为我们只做乘法和取模，直接计算即可。由于 $k$ 可能很大，必须用快速幂。

注意：等差数列的项可能超过 long long 范围，需要在计算过程中取模。等差数列公式 $a + (k-1) \times d$ 可能很大，取模时注意负数。