#include<cstdio>

#define N_MAX 666013

int inm(int a[3][3], int b[3][3], int rez[3][3]) {

  int rez2[3][3] = {0};
  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 3; ++j) {
      for(int k = 0; k < 3; ++k)
        rez2[i][j] += a[i][k]* b[k][j] % N_MAX;
    }
  }
  for(int i = 0; i < 3; ++i)
    for(int j = 0; j < 3; ++j) {
      rez[i][j] = rez2[i][j];
    }
}

const int I[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

void cpy(const int a[3][3], int b[3][3]) {
  for(int i = 0; i < 3; ++i)
    for(int j = 0; j < 3; ++j)
      b[i][j] = a[i][j];
}

void put(int a[3][3], int p, int rez[3][3]) {
  cpy(I, rez);
  for(; p; p >>= 1) {
    if(p & 1) {
      inm(a, rez, rez);
    }
    inm(a, a, a);
  }
}

void citire(int m[3][3]) {
  for(int i = 0; i < 3; ++i)
    for(int j = 0; j < 3; ++j)
      fscanf(stdin, "%d", &m[i][j]);
  fprintf(stdout, "\n");
}

void afis(const int m[3][3]) {
  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 3; ++j)
      fprintf(stdout, "%3d ", m[i][j]);
    fprintf(stdout, "\n");
  }
}

int main() {

  FILE *in = fopen("iepuri.in", "r");
  FILE *out = fopen("iepuri.out", "w");

  int T;
  int n;
  int M[3];

  int rez[3][3];

  fscanf(in, "%d", &T);
  while(T--) {
    int KM[3][3] = {{0, 1, 0}, {0, 0, 1}, {0, 0, 0}};
    fscanf(in, "%d%d%d%d%d%d%d", &M[2], &M[1], &M[0], &KM[0][0], &KM[1][0], &KM[2][0], &n);

    put(KM, n - 2, rez);
    int sol = 0;
    for(int i = 0; i < 3; ++i)
      sol += M[i] * rez[i][0] % N_MAX;
    fprintf(out, "%d\n", sol);
  }

  return 0;
}