#include <iostream>
#include <fstream>
#define N 2000000000
#define L 3
#define MOD 666013

using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

int* row_multiply(int* r,int* c[])
{
	int *ret=new int[L];
	unsigned long long sum;
	for(int i=0;i<L;i++)
	{
		sum=0;
		for(int j=0;j<L;j++)
			sum+=1ULL*r[j]*c[j][i];
		ret[i]=(int)(sum%MOD);
	}
	return ret;
}

int** matrix_multiply(int* a[],int* b[])
{
	int** ret=new int*[L];
	for(int i=0;i<L;i++)
		ret[i]=row_multiply(a[i],b);
	return ret;
}

int* C[L];

void free_matrix(int** m)
{
	if(m==C)
		return;
	for(int i=0;i<L;i++)
		delete m[i];
	delete m;
}

int** exp(int n)
{
	int **ret,**half,**half2;
	if(n==1)
		return C;
	half=half2=exp(n/2);
	if(n&1)
		half2=matrix_multiply(C,half);
	ret=matrix_multiply(half,half2);
	free_matrix(half);
	if(n&1)
		free_matrix(half2);
	return ret;
}

void print_matrix(int **m)
{
	for(int i=0;i<L;i++)
	{
		for(int j=0;j<L;j++)
			cout<<m[i][j]<<' ';
		cout<<'\n';
	}
}

int main()
{
	int t,n,i,j,r[L],**m,*ret;

	for(i=0;i<L;i++)
		C[i]=new int[L]();
	C[1][0]=C[2][1]=1;
	// print_matrix(C);
	f>>t;

	for(i=0;i<t;i++)
	{
		f>>r[0]>>r[1]>>r[2]>>C[2][2]>>C[1][2]>>C[0][2]>>n;
		if(n<=2)
		{
			g<<r[n]<<'\n';
			continue;
		}
		m=exp(n-2);
		// print_matrix(m);
		ret=row_multiply(r,m);
		free_matrix(m);
		g<<ret[L-1]<<'\n';
		delete ret;
	}
}