#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
#include <iostream>
using namespace std;
#define FOR(i,a,b) for (i=a;i<=b;i++)
#define fori(it,v) for (it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
#define zlate 666013
FILE *in,*out;
long long x, y, z, aj, bj, n, b[5][5], a[5][5], b1[5][5], i, j, nrt, k, c, ct[5][5], test, teste;
void mul(long long a[5][5], long long b[5][5])
{
	int i,j,k;
	FOR(i,1,3)
		FOR(j,1,3)
			FOR(k,1,3)
				b1[i][j]=(b1[i][j]+(a[i][k]*b[k][j])%zlate)%zlate;
	FOR(i,1,3)
		FOR(j,1,3)
			a[i][j]=b1[i][j],b1[i][j]=0;
}
void prod(int n)
{
	while (n)
	{
		if (n & 1 == 1)
			mul(ct, b);
		
		mul(b, b);
		n >>= 1;
	}
}
void gol()
{
	int i,j;
	FOR(i,1,3)
		FOR(j,1,3)
			a[i][j]=b[i][j]=ct[i][j]=0;
}
int main()
{
	int i,j;
	in=fopen("iepuri.in","r");
	out=fopen("iepuri.out","w");
	scanf("%lld", &teste);
	for(;teste;teste--)
	{
		fscanf(in,"%lld%lld%lld%lld%lld%lld%lld", &a[1][1], &a[1][2], &a[1][3], &b[3][3], &b[2][3], &b[1][3], &n);
		b[2][1] = 1, b[3][2] = 1;
		FOR(i,1,3)
			FOR(j,1,3)
				if (i == j)
					ct[i][j] = 1;
				else
					ct[i][j] = 0;
		
		n -= 2; 
		prod(n);
		mul(a, ct);
		fprintf(out,"%lld\n", a[1][3]);
		gol();
	}	
	fclose(in);
	fclose(out);
	return 0;
}