不知道你是否还记得嘴硬的圈圈？当然这题跟圈圈没关系，这回要讲的是圈圈的朋友，小啊晶的故事。小啊晶与不爱学习还爱嘴硬的圈圈不同，他十分的爱学习，今天他竟然学到了等比数列和等差数列！聪明的小啊晶发现给出一个数列的前三项，就能确定他是等比还是等差！多么神奇啊！！于是聪明的小阿晶决定考考你，如果给定一个一定是等比或者等差数列的前三项，你能求出其中第K项的值吗？如果第K项过大，请对200907取模。

Input

第一行一个整数 T，表示有 T 组测试数据； 对于每组测试数据，输入前三项 a, b, c，然后输入 k。 对于全部数据，$1\le T\le 100,1\le a\le b\le c\le 10^9,1\le k\le 10^9$。

Output

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

Samples

2
1 2 3 5
1 2 4 5

5
16

Limitation

1s, 1024KiB for each test case.