Description

BSNY is learning about arithmetic and geometric sequences. Given the first three terms of a sequence, it can be determined whether it is an arithmetic or geometric sequence. Now, given the first three terms of a sequence, which is either arithmetic or geometric, can you find the value of the $k$-th term? If the value is too large, take modulo $200907$.

Input Format

The first line contains an integer $T$, indicating the number of test cases.

For each test case, input the first three terms $a, b, c$, followed by $k$.

Output Format

For each test case, output the value of the $k$-th term modulo $200907$.

Sample 1

The first sequence is arithmetic, and the second is geometric.

2
1 2 3 5
1 2 4 5

5
16

Constraints and Hints

For all data, $1\le T\le 100,1\le a\le b\le c\le 10^9,1\le k\le 10^9$.