hdu2817

/*
分析:
1つの記号WAを1回間違えて、壁にぶつかって行ったほうがいい...
2点でしょう、等比数列の場合です.くどくど言わないで、
ご飯を食べに行きました...囧~
                                                    2013-02-26
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define e 200907

__int64 a,b,c,k;
void solve1()
{
	__int64 dir,ans;
	dir=(c-b)%e;
	k=(k-1)%e;
	a%=e;
	ans=(a+k*dir)%e;
	printf("%I64d
",ans);
}
void solve2()
{
	if(k==1)	printf("%I64d
",a%e);

	__int64 q,ans;
	q=(c/b)%e;
	a%=e;
	k--;

	__int64 t,tt,temp;
	t=k;tt=2;
	temp=q;
	ans=a;
	while(0<t)
	{
		while(tt<t)
		{
			temp=(temp*temp)%e;
			tt*=2;
		}
		ans=(ans*temp)%e;
		t-=tt/2;
		tt=2;
		temp=q;
	}
	printf("%I64d
",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k);
		if(c-b==b-a)	solve1();
		else			solve2();
	}
	return 0;
}