#include <fstream>
#include <cstring>

using namespace std;

#define mod1 666013

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

int a[5][5], sol[5][5], c[5][5];

inline void Inmultire(int a1[5][5], int a2[5][5]) {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            c[i][j] = 0;

            for (int k = 1; k <= 3; k++) {
                c[i][j] += (1LL * a1[i][k] * a2[k][j]) % mod1;
                c[i][j] %= mod1;
            }
        }
    }

    for (int i = 1; i <= 3; i++){
        for (int j = 1; j <= 3; j++)
            a1[i][j] = c[i][j];
    }
}

inline void Ridicare(int a[5][5], int n) {
    while (n) {
         if (n & 1) {
            n--;
            Inmultire(sol, a);
         }
         n >>= 1;

         Inmultire(a, a);
    }
}

inline void Read() {
    int x, y, z, A, B, C, n, T;

    fin >> T;

    while (T--) {
        fin >> z >> y >> x >> A >> B >> C >> n; n++;

        if (n == 1) {
            fout << x << "\n";
            continue;
        }
        else if (n == 2) {
            fout << y << "\n";
            continue;
        }
        else if (n == 3) {
            fout << z << "\n";
            continue;
        }

        a[1][1] = 0; a[1][2] = 0; a[1][3] = C;
        a[2][1] = 1; a[2][2] = 0; a[2][3] = B;
        a[3][1] = 0; a[3][2] = 1; a[3][3] = A;

        memset(sol, 0, sizeof(sol));

        sol[1][1] = sol[2][2] = sol[3][3] = 1;

        Ridicare(a, n - 3);

        fout << ((1LL * sol[1][3] * z) % mod1+ (1LL * sol[2][3] * y) + (1LL * sol[3][3] * x) % mod1) % mod1 << "\n";
    }
}

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}