#include <iostream>
#include <fstream>
using namespace std;
const int rest=666013;
//p[i] = 2^i
long long p[1000][4][4], b[4][4];
int calcputeri() {
     long long i, j, k, a[4][4];
     for(i=1; i<32; i++) {
          a[1][1]=p[i-1][1][1]*p[i-1][1][1] + p[i-1][1][2]*p[i-1][2][1] + p[i-1][1][3]*p[i-1][3][1];
          a[1][2]=p[i-1][1][1]*p[i-1][1][2] + p[i-1][1][2]*p[i-1][2][2] + p[i-1][1][3]*p[i-1][3][2];
          a[1][3]=p[i-1][1][1]*p[i-1][1][3] + p[i-1][1][2]*p[i-1][2][3] + p[i-1][1][3]*p[i-1][3][3];
          a[2][1]=p[i-1][2][1]*p[i-1][1][1] + p[i-1][2][2]*p[i-1][2][1] + p[i-1][2][3]*p[i-1][3][1];
          a[2][2]=p[i-1][2][1]*p[i-1][1][2] + p[i-1][2][2]*p[i-1][2][2] + p[i-1][2][3]*p[i-1][3][2];
          a[2][3]=p[i-1][2][1]*p[i-1][1][3] + p[i-1][2][2]*p[i-1][2][3] + p[i-1][2][3]*p[i-1][3][3];
          a[3][1]=p[i-1][3][1]*p[i-1][1][1] + p[i-1][3][2]*p[i-1][2][1] + p[i-1][3][3]*p[i-1][3][1];
          a[3][2]=p[i-1][3][1]*p[i-1][1][2] + p[i-1][3][2]*p[i-1][2][2] + p[i-1][3][3]*p[i-1][3][2];
          a[3][3]=p[i-1][3][1]*p[i-1][1][3] + p[i-1][3][2]*p[i-1][2][3] + p[i-1][3][3]*p[i-1][3][3];
          for(j=1; j<=3; j++) {
               for(k=1; k<=3; k++) {
                    p[i][j][k]=a[j][k]%rest;
               }
          }
     }
}

void inmulteste(long long a[4][4]) {
    int mn, mp, c[4][4];
    for(mn=1; mn<=3; mn++) {
         for(mp=1; mp<=3; mp++) {
              c[mn][mp]=b[mn][mp];
         }
    }          
    b[1][1]=c[1][1]*a[1][1] + c[1][2]*a[2][1] + c[1][3]*a[3][1];
    b[1][1]%=rest;
    b[1][2]=c[1][1]*a[1][2] + c[1][2]*a[2][2] + c[1][3]*a[3][2];
    b[1][2]%=rest;
    b[1][3]=c[1][1]*a[1][3] + c[1][2]*a[2][3] + c[1][3]*a[3][3];
    b[1][3]%=rest;
    b[2][1]=c[2][1]*a[1][1] + c[2][2]*a[2][1] + c[2][3]*a[3][1];
    b[2][1]%=rest;
    b[2][2]=c[2][1]*a[1][2] + c[2][2]*a[2][2] + c[2][3]*a[3][2];
    b[2][2]%=rest;
    b[2][3]=c[2][1]*a[1][3] + c[2][2]*a[2][3] + c[2][3]*a[3][3];
    b[2][3]%=rest;
    b[3][1]=c[3][1]*a[1][1] + c[3][2]*a[2][1] + c[3][3]*a[3][1];
    b[3][1]%=rest;
    b[3][2]=c[3][1]*a[1][2] + c[3][2]*a[2][2] + c[3][3]*a[3][2];
    b[3][2]%=rest;
    b[3][3]=c[3][1]*a[1][3] + c[3][2]*a[2][3] + c[3][3]*a[3][3];
    b[3][3]%=rest;
}

int main() {
    fstream f1, f2;
    long long x, y, z, as, s, cs, n, n1, i, j, t, k, f, unu[4][4], q;
    f1.open("iepuri.in", ios::in);
    f2.open("iepuri.out", ios::out);
    f1>>t;
    for(q=1; q<=t; q++) {
         f1>>x>>y>>z>>as>>s>>cs>>n;
         p[0][1][1]=0; p[0][1][2]=1; p[0][1][3]=0;
         p[0][2][1]=0; p[0][2][2]=0; p[0][2][3]=1;
         p[0][3][1]=cs; p[0][3][2]=s; p[0][3][3]=as;
         calcputeri();
         //iau n si il descompun
         //initializez b
         b[1][1]=1; b[1][2]=0; b[1][3]=0;
         b[2][1]=0; b[2][2]=1; b[2][3]=0;
         b[3][1]=0; b[3][2]=0; b[3][3]=1;
         j=0; n1=n;
         while(n1) {
              if(n1%2==1) {
                   //s=1<<j;
                   for(f=1; f<=3; f++) {
                        for(k=1; k<=3; k++) {
                             unu[f][k]=p[j][f][k];
                        }
                   }         
                   inmulteste(unu);
              }
              j++; n1=n1/2;
         }
         //am in b = p[0] la n;
         //i(n+2) = b[3][1]*x + b[3][2]*y + b[3][3]*z;
         f2<<(b[1][1]*x + b[1][2]*y + b[1][3]*z)%rest;
         f2<<endl;
    }
    f1.close(); f2.close();
    return 0;
}