Description

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

Input

第一行一个整数?T，表示有?T?组测试数据；

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

Output

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

Sample Input

2
1 2 3 5
1 2 4 5

Sample Output

5
16

HINT

?

样例说明

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

数据范围与提示

对于全部数据，1≤T≤100,1≤a≤b≤c≤109,1≤k≤109

事实上,不开long long会玄学WA.

#include <iostream>

using namespace std;

long long slowmul(long long a, long long b) // 慢速乘有防止溢出的作用
{
	long long res = 0;
	
	while (b)
	{
		if (b & 1)
		{
			res += a;
			res %= 200907;
		}
		a <<= 1;
		b >>= 1;
	}
	
	return res;
}

long long quickpow(long long a, long long b) // 快速幂模板
{
	long long res = 1;
	
	while (b)
	{
		if (b & 1)
		{
			res *= a;
			res %= 200907;
		}
		a *= a;
		a %= 200907;
		b >>= 1;
	}
	
	return res;
}

int main(void)
{
	long long t, a, b, c, d;
	
	scanf("%lld", &t);
	while (t--)
	{
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		if (a - b == b - c) // 如果是等差数列
		{
			printf("%lld\n", (a + slowmul(b - a, d - 1)) % 200907); // 慢速乘求第K个数
		}
		else // 如果不是等差数列,则是等比数列
		{
			printf("%lld\n", (a * quickpow(b / a, d - 1)) % 200907); // 快速幂求第K个数
		}
	}
	
	return 0;
}

?