题目描述

已知序列的前三项，这个序列要么是等差数列，要么是等比数列。请根据给定前三项判断序列类型，并求出第 $k$ 项的值，结果对 $200907$ 取模。

输入格式

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

每组数据一行，包含四个整数 $a, b, c, k$，分别表示前三项和第 $k$ 项的位置。

输出格式

对于每组数据，输出一个整数，表示第 $k$ 项的值对 $200907$ 取模的结果。

2
1 2 3 5
1 2 4 5

5
16

提示

样例 1 说明

• 第一组：等差数列 $1, 2, 3, 4, 5, \dots$，第 $5$ 项为 $5$。
• 第二组：等比数列 $1, 2, 4, 8, 16, \dots$，第 $5$ 项为 $16$。

数据规模与约定

对于全部的测试点，保证 $1 \leq T \leq 100$，$1 \leq a \leq b \leq c \leq 10^9$，$1 \leq k \leq 10^9$。