// 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)

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

typedef long long ll;

void mult3 (ll A[3][3], ll B[3][3], ll C[3][3]) {
  ll D[3][3]; int 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"); 
  ll Y[3],P[3][3],M[3][3],a,b; int N,T,p;
  fscanf(fi,"%d",&T); for ( ; 0<T; --T ) {
    fscanf(fi,"%lld %lld %lld %lld %lld %lld %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 >= p ) {
      if ( 0 != ( N&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,"%lld\n",a);
  } fclose(fi); fclose(fo); return 0;
}