#include <bits/stdc++.h>
using namespace std;
ifstream f ("iepuri.in");
ofstream g ("iepuri.out");
const int mod=666013;
long long a[4][4],v[4][4],p,k,n,x,y,z,aa,bb,cc,t;
void mult(long long a[4][4],long long b[4][4])
{
    long long c[4][4]={0};
    for(int i=1;i<=3;++i)
    {
        for(int j=1;j<=3;++j)
        {
            for(int k=1;k<=3;++k)
            {
                c[i][j]+=a[i][k]*b[k][j];
                c[i][j]%=mod;
            }
        }
    }
    for(int i=1;i<=3;++i)
    {
        for(int j=1;j<=3;++j) a[i][j]=c[i][j];
    }
}
long long solve()
{
    f>>x>>y>>z>>aa>>bb>>cc>>n;
    if(n==0) return x;
    if(n==1) return y;
    if(n==2) return z;
	n=(n-2);
	memset(a,0,sizeof(a));
	a[1][1]=a[2][2]=a[3][3]=1;
	v[1][1]=aa;
	v[1][2]=bb;
	v[1][3]=cc;
    v[2][1]=1;
	v[2][2]=0;
	v[2][3]=0;
	v[3][1]=0;
	v[3][2]=1;
	v[3][3]=0;
	while(n)
	{
		if(n&1) mult(a,v);
		mult(v,v);
		n>>=1;
	}
	long long sol=z*a[1][1]+y*a[1][2]+x*a[1][3];
	return (sol%mod);
}
int main()
{
	f>>t;
	while(t--) g<<solve()<<'\n';
	return 0;
}