#include <cstdio>
#include <cstring>
#define mod 666013

using namespace std;
int n,S[4][4],v[4][4],X,Y,Z,A,B,C;
inline void Init(){
        S[1][1] = X;
        S[1][2] = Y;
        S[1][3] = Z;

        v[1][3] = C;
        v[2][3] = B;
        v[3][3] = A;

        v[3][2] = v[2][1] = 1;
}
inline void prod(int a[4][4],int b[4][4],int c[4][4]){
 int i,j,k;
  for(i = 1; i <= 3; ++i)
    for(j = 1; j <= 3; ++j)
     for(k = 1; k <= 3; ++k)
      c[i][j] = (c[i][j] + a[i][k]*1LL*b[k][j])%mod;
}
int pow(long long n){
 int i,b[4][4];
 while(n){
    if(n&1){
            --n;
        memset(b,0,sizeof(b));
        prod(S,v,b);
        memcpy(S,b,sizeof(b));
    }
    memset(b,0,sizeof(b));
    prod(v,v,b);
    memcpy(v,b,sizeof(b));
    n/=2;
 }
 return S[1][3]%mod;
}
int main(){
    int t,j;
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d\n",&t);
    while(t--){
        scanf("%d%d%d%d%d%d%d\n",&X,&Y,&Z,&A,&B,&C,&n);
      Init();
      j = pow(n-2);

      printf("%d\n",j);

      memset(S,0,sizeof(S));
      memset(v,0,sizeof(v));
    }
    return 0;
}