#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

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

struct Mat {
    long long int mat[3][3];
};

Mat null,init;

int f1,f2,f3,a,b,c,n;

void initializare();
Mat pow(Mat mat,int n);
Mat prod(Mat a,Mat b);

int main()
{int t;
 Mat ret;
 fin>>t;
 while(t--)
      {fin>>f1>>f2>>f3;
       fin>>a>>b>>c;
       fin>>n;
       n++;
       initializare();
       init.mat[0][0]=a;init.mat[1][0]=b;init.mat[2][0]=c;
       ret=pow(init,n-3);
       fout<<(f3*ret.mat[0][0]+f2*ret.mat[1][0]+f1*ret.mat[2][0])%MOD<<'\n';
      }

 return 0;
}
void initializare()
{int i,j;
 for(i=0;i<3;i++)
     for(j=0;j<3;j++)
         null.mat[i][j]=init.mat[i][j]=0;
 for(i=0;i<3;i++)
     null.mat[i][i]=1;
 for(i=0;i<2;i++)
     init.mat[i][i+1]=1;
}
Mat pow(Mat mat,int n)
{if(!n)
    return null;
 if(n & 1)
    return prod(mat,pow(prod(mat,mat),n >> 1));
 return pow(prod(mat,mat),n >> 1);
}
Mat prod(Mat a,Mat b)
{Mat ret;
 ret.mat[0][0]=(a.mat[0][0]*b.mat[0][0]+a.mat[0][1]*b.mat[1][0]+a.mat[0][2]*b.mat[2][0])%MOD;
 ret.mat[0][1]=(a.mat[0][0]*b.mat[0][1]+a.mat[0][1]*b.mat[1][1]+a.mat[0][2]*b.mat[2][1])%MOD;
 ret.mat[0][2]=(a.mat[0][0]*b.mat[0][2]+a.mat[0][1]*b.mat[1][2]+a.mat[0][2]*b.mat[2][2])%MOD;
 ret.mat[1][0]=(a.mat[1][0]*b.mat[0][0]+a.mat[1][1]*b.mat[1][0]+a.mat[1][2]*b.mat[2][0])%MOD;
 ret.mat[1][1]=(a.mat[1][0]*b.mat[0][1]+a.mat[1][1]*b.mat[1][1]+a.mat[1][2]*b.mat[2][1])%MOD;
 ret.mat[1][2]=(a.mat[1][0]*b.mat[0][2]+a.mat[1][1]*b.mat[1][2]+a.mat[1][2]*b.mat[2][2])%MOD;
 ret.mat[2][0]=(a.mat[2][0]*b.mat[0][0]+a.mat[2][1]*b.mat[1][0]+a.mat[2][2]*b.mat[2][0])%MOD;
 ret.mat[2][1]=(a.mat[2][0]*b.mat[0][1]+a.mat[2][1]*b.mat[1][1]+a.mat[2][2]*b.mat[2][1])%MOD;
 ret.mat[2][2]=(a.mat[2][0]*b.mat[0][2]+a.mat[2][1]*b.mat[1][2]+a.mat[2][2]*b.mat[2][2])%MOD;
 return ret;
}