#include <iostream>
#include <fstream>
#include <vector>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;
using ll = long long;
const ll MOD = 666013;

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

ll A, B, C;

struct mat{
    ll m[3][3];
};

mat M = {
    { {0, 1, 0},
      {0, 0, 1},
      {0, 0, 0} }
};

mat inm(mat a, mat b){
    mat c = {
        { {0, 0, 0},
          {0, 0, 0},
          {0, 0, 0} }
    };

    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 3; k++){
                c.m[i][j] += (a.m[i][k] * b.m[k][j]) % MOD;
                c.m[i][j] %= MOD;
            }
        }
    }
    return c;
}

mat exp_rpd(mat b, int e){
    mat p = {
        { {1, 0, 0},
          {0, 1, 0},
          {0, 0, 1} }
    };

    while(e){
        if(e % 2) p = inm(p, b);
        b = inm(b, b);
        e /= 2;
    }
    return p;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; in >> t;
    for(int ii = 0; ii < t; ii++){
        ll X, Y, Z, N;
        in >> X >> Y >> Z >> A >> B >> C >> N;
        
        mat sol = {
            { {Z, Y, X},
              {0, 0, 0},
              {0, 0, 0} }
        };

        if(N == 0){
            out << X << '\n';
            continue;
        }

        if(N == 1){
            out << Y << '\n';
            continue;
        }

        if(N == 2){
            out << Z << '\n';
            continue;
        }

        M.m[0][0] = A;
        M.m[1][0] = B;
        M.m[2][0] = C;

        // cout << "sol : \n";
        // for(int i = 0; i < 3; i++){
        //     for(int j = 0; j < 3; j++) cout << sol.m[i][j] << " ";
        //     cout << '\n';
        // }

        // for(int i = 3; i <= N; i++){
        //     sol = inm(sol, M);
        // }
        sol = inm(sol, exp_rpd(M, N - 3 + 1));

        // cout << "sol : \n";
        // for(int i = 0; i < 3; i++){
        //     for(int j = 0; j < 3; j++) cout << sol.m[i][j] << " ";
        //     cout << '\n';
        // }

        out << sol.m[0][0] << '\n';
   }

    return 0;
}