// M=[A B C ; 1 0 0 ; 0 1 0 ]
// Y(n)=[X(n+2) X(n+1) X(n) ] Y(n+1)=M Y(n)
// Y(1)=M Y(0) ; Y(2)=M^2 Y(0) ; Y(n-2)=M^{n-2} Y(0)

#include<cstdio>
using namespace std;
int const Mo=666013;

void mult3 (int A[3][3], int B[3][3], int C[3][3]) {
  int D[3][3],i,j,k,z,s;
  for ( i=0; 3>i; ++i ) for ( j=0; 3>j; ++j ) {
    for ( k=0, s=0; 3>k; ++k ) {
      z=A[i][k]*B[k][j]; z%=Mo; s+=z; s%=Mo;
    }
    D[i][j]=s;
  }
  for ( i=0; 3>i; ++i ) {
    for ( j=0; 3>j; ++j ) {
      C[i][j]=D[i][j];
    }
  }
}


int main ( ) {
  FILE * fi=fopen("iepuri.in", "r"), * fo=fopen("iepuri.out","w"); 
  int Y[3],P[3][3],M[3][3],N,T,a,b,p;
  fscanf(fi,"%d",&T); for ( ; 0<T; --T ) {
    fscanf(fi,"%d %d %d %d %d %d %d",&Y[2],&Y[1],&Y[0],
      &P[0][0],&P[0][1],&P[0][2],&N); P[1][0]=1; P[1][1]=0;
    P[1][2]=0;P[2][0]=0;P[2][1]=1;P[2][2]=0;M[0][0]=1;
    M[0][1]=0;M[0][2]=0;M[1][0]=0;M[1][1]=1;M[1][2]=0;
    M[2][0]=0;M[2][1]=0;M[2][2]=1;p=1;
    while ( (N-2) >= p ) {
      if ( 0 != ( (N-2)&p ) ) {
        mult3(P,M,M);
      }
      mult3(P,P,P); p*=2;
    }
    a=(M[0][0]*Y[0])%Mo; b=(M[0][1]*Y[1])%Mo;a+=b;a%=Mo;
    b=(M[0][2]*Y[2])%Mo; a+=b; a%=Mo; fprintf(fo,"%d\n",a);
  } fclose(fi); fclose(fo); return 0;
}