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

Description

等差数列和等比数列

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

输入格式

第一行一个整数 $T$, 表示有 $T$ 组测试数据;

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

输出格式

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

样例

输入:

    2
    1 2 3 5
    1 2 4 5
    

输出:

    5
    16
    

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

数据范围与提示

对于全部数据, $1 \leq T \leq 100,1 \leq a \leq b \leq c \leq 10^9, 1 \leq k \leq 10^9$ 。

Source