#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream in("iepuri.in");
ofstream out("iepuri.out");

long long n;
int t;//date intrare
int iepuri[4][4], produs[4][4];

void inmultire(int a[4][4], int b[4][4]){
    int aux[4][4];
    memset(aux,0,sizeof(aux));
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++){
            long long suma = 0;
            for(int k = 1; k <= 3;k++)
                suma = suma + (1LL * a[i][k] * b[k][j]) % 666013;
            aux[i][j] = suma % 666013;
        }
    for(int i = 1; i <= 3; i++)
      for(int j = 1; j <= 3; j++)
          b[i][j] = aux[i][j];
    memcpy(b,aux,sizeof(aux));
}

void rezolvare(){
    while(n){
        if(n % 2 == 1)
          inmultire(produs, iepuri);
        inmultire(produs, produs);
        n /= 2;
    }
}

void afisare(){
    out << iepuri[1][1]<<"\n";
}

void citire(){
    in >> t;
    for(int i = 1; i <= t; i++){
      memset(iepuri,0,sizeof(iepuri));
      memset(produs,0,sizeof(produs));
      int x,y,z,a,b,c;
      in >> x >> y >> z >> a >> b >> c >> n;
      n -= 2;
      iepuri[1][1] = z;
      iepuri[2][1] = y;
      iepuri[3][1] = x;
      produs[1][1] = a;
      produs[1][2] = b;
      produs[1][3] = c;
      produs[2][1] = 1;
      produs[3][2] = 1;
      rezolvare();
      afisare();
    }
}

int main()
{
    citire();
    return 0;
}