#include <fstream>
using namespace std;

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

const int mod=666013;
unsigned long long A[2][4], M[4][4], aux[4][4], x, y, z, a, b, c, n;
int t, i, I, J, K;

int main()
{	f>>t;
	for (; t; --t)
	{	f>>x>>y>>z>>a>>b>>c>>n;
		A[1][1]=x;
		A[1][2]=y;
		A[1][3]=z;
		M[1][1]=M[1][2]=M[2][2]=M[3][1]=0;
		M[1][3]=c;
		M[2][1]=1;
		M[2][3]=b;
		M[3][2]=1;
		M[3][3]=a;
		for (i=0; (1<<i)<=(n-2); ++i)
		{	if ((1<<i)&(n-2))
			{	for (I=1; I<=1; ++I)
					for (J=1; J<=3; ++J)
					{	aux[I][J]=0;
						for (K=1; K<=3; ++K)
							aux[I][J]=(aux[I][J]+(A[I][K]*M[K][J])%mod)%mod;
					}
				for (I=1; I<=1; ++I)
					for (J=1; J<=3; ++J) A[I][J]=aux[I][J];
			}
			for (I=1; I<=3; ++I)
				for (J=1; J<=3; ++J)
				{	aux[I][J]=0;
					for (K=1; K<=3; ++K)
						aux[I][J]=(aux[I][J]+(M[I][K]*M[K][J])%mod)%mod;
				}
			for (I=1; I<=3; ++I)
				for (J=1; J<=3; ++J) M[I][J]=aux[I][J];
		}
		g<<A[1][3]<<'\n';
	}
    return 0;
}