#include <fstream>
using namespace std;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

#define MOD 666013
#define int long long

int a[4][4],b[4][4],c[4][4];

void inm(int x[4][4],int y[4][4]){
	int i,j,k;
    for(i=0;i<4;i++) for(j=0;j<4;j++) c[i][j]=0;
	for(i=1;i<=3;i++){
		for(j=1;j<=3;j++){
			for(k=1;k<=3;k++){
                c[i][j]+=((x[i][k]%MOD)*(y[k][j]%MOD))%MOD;c[i][j]%=MOD;
			}
		}
    }
	for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
			y[i][j]=c[i][j];
}


void solve(){
    int i,j,n;
    for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=b[i][j]=0;
    cin>>b[3][1]>>b[2][1]>>b[1][1]>>a[1][1]>>a[1][2]>>a[1][3]>>n;
    n-=2;
    a[2][1]=a[3][2]=1;
    for(i=n;i>0;i/=2){
        if(i%2) inm(a,b);
        inm(a,a);
    }
    cout<<b[1][1]<<"\n";
}

signed main()
{
	int t,l;
	cin>>t;
	while(t--) solve();
}