学步园

#include<stdio.h>
#define inf 200907
__int64 a[4],n;
void solve1()
{
	__int64 d;
	d=(a[2]-a[1])%inf;
	printf("%I64d\n",(a[1]%inf+d*(n-1)%inf)%inf);
}
void solve2()
{
	__int64 q,num,t,sum,count;
	if(n==1)
	{printf("I64d\n",a[1]%inf);return ;}
	q=(a[2]/a[1])%inf;
	sum=a[1]%inf;
	t=n-1;num=4;
	count=q;
	while(t>0)
	{
		while(num<t)
		{
			count=(count*count)%inf;
			count=(count*count)%inf;
			num*=4;
		}
		sum=(sum*count)%inf;
		t=t-num/4;
		count=q;
		num=4;
	}
	printf("%I64d\n",sum);
}
int main()
{
	int i,j,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%I64d%I64d%I64d%I64d",&a[1],&a[2],&a[3],&n);
		if(a[3]-a[2]==a[2]-a[1])
			solve1();
		else solve2();
	}
	return 0;
}