#include<fstream>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long long t,a,b,c,x,y,z,i,n,mod=666013;
long long a11,a12,a13,a21,a22,a23,a31,a32,a33;
void expmat(long long n,long long &a11,long long &a12,long long &a13,long long &a21,long long &a22,long long &a23,long long &a31,long long &a32,long long &a33){
    long long b11,b12,b13,b21,b22,b23,b31,b32,b33;
    if (n==1){
       a11=a;a12=b;a13=c;
       a21=1;a22=0;a23=0;
       a31=0;a32=1;a33=0;
       return;
    }
      else
        if (n%2==0){
           expmat(n/2,b11,b12,b13,b21,b22,b23,b31,b32,b33);
           a11=((b11*b11)%mod+(b12*b21)%mod+(b13*b31)%mod)%mod;
           a12=((b11*b12)%mod+(b12*b22)%mod+(b13*b32)%mod)%mod;
           a13=((b11*b13)%mod+(b12*b23)%mod+(b13*b33)%mod)%mod;
           a21=((b21*b11)%mod+(b22*b21)%mod+(b23*b31)%mod)%mod;
           a22=((b21*b12)%mod+(b22*b22)%mod+(b23*b32)%mod)%mod;
           a23=((b21*b13)%mod+(b22*b23)%mod+(b23*b33)%mod)%mod;
           a31=((b31*b11)%mod+(b32*b21)%mod+(b33*b31)%mod)%mod;
           a32=((b31*b12)%mod+(b32*b22)%mod+(b33*b32)%mod)%mod;
           a33=((b31*b13)%mod+(b32*b23)%mod+(b33*b33)%mod)%mod;
        }
          else{
            expmat(n-1,b11,b12,b13,b21,b22,b23,b31,b32,b33);
            a11=((b11*a)%mod+b12%mod)%mod;
            a12=((b11*b)%mod+b13%mod)%mod;
            a13=(b11*c)%mod;
            a21=((b21*a)%mod+b22%mod)%mod;
            a22=((b21*b)%mod+b23%mod)%mod;
            a23=(b21*c)%mod;
            a31=((b31*a)%mod+b32%mod)%mod;
            a32=((b31*b)%mod+b33%mod)%mod;
            a33=(b31*c)%mod;
          }
}
int main(){
    fin>>t;
    for (i=1;i<=t;i++){
        fin>>x>>y>>z>>a>>b>>c>>n;
        expmat(n-2,a11,a12,a13,a21,a22,a23,a31,a32,a33);
        fout<<((a11*z)%mod+(a12*y)%mod+(a13*x)%mod)%mod<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}