F. *【快速幂】序列的第 k 项

传统题

1000ms

512MiB

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

【题意】

已知一个序列（等差或等比序列）的前 $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

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