#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

int p[3][3],a[3][3],b[3][3],t,n,X,Y,Z,A,B,C;


int copie(int a[3][3],int b[3][3]){
    int i,j;
    for(i=0;i<=2;i++)
        for(j=0;j<=2;j++)
            a[i][j]=b[i][j];

}

int produs(int a[3][3],int b[3][3], int c[3][3]){
    int i,j,k;
    for(i=0;i<=2;i++){
        for(j=0;j<=2;j++){
            c[i][j]=0;
            for(k=0;k<=2;k++){
                c[i][j]=(c[i][j]+ 1LL*a[i][k] * b[k][j])%MOD;
            }
        }
    }
}

int LogP(int a[3][3],int p[3][3],int n){
    int i,j;
    p[0][0]=X;
    p[0][1]=Y;
    p[0][2]=Z;
    while(n>0){
        if(n%2==1){
            produs(p,a,b);
            copie(p,b);
        }
        n/=2;
        produs(a,a,b);
        copie(a,b);

    }
}

int main()
{
    int i,sol;
    fin >> t;
    while(t>0){
        fin >> X >> Y >> Z >> A >> B >> C >> n;
        a[0][0]=a[0][1]=a[1][1]=a[2][0]=0;
        a[1][0]=a[2][1]=1;
        a[0][2]=C;
        a[1][2]=B;
        a[2][2]=A;
        LogP(a,p,n-2);
        sol= p[0][2] % MOD;
        fout << sol << "\n";
        t--;
    }
    return 0;
}