#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>

using namespace std;

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

#define MOD 666013

int t;

int smart_mul(int a, int b, int mod) {
    return (1LL * (a % mod) * (b % mod)) % mod;
}

void matrix_copy(int dst[3][3], int src[3][3]) {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            dst[i][j] = src[i][j];
        }
    }
}

// res = a * b
void matrix_mul(int res[][3], int a[][3], int b[][3], int n1,
                int m1, int n2, int m2) {
    if (m1 != n2) {
        return;
    }

    int res_aux[3][3] = {0};
    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < m2; ++j) {
            for (int k = 0; k < m1; ++k) {
                res_aux[i][j] += smart_mul(a[i][k], b[k][j], MOD);
                res_aux[i][j] %= MOD;
            }
        }
    }

    matrix_copy(res, res_aux);
}

void log_power(int res[][3], int mat[][3], int power) {
    
    int res_tmp[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    while (power > 0) {
        if (power & 1) {
            // result *= mat;
            matrix_mul(res_tmp, mat, res_tmp, 3, 3, 3, 3);
 
        }
        // mat *= mat
        matrix_mul(mat, mat, mat, 3, 3, 3, 3);
        power >>= 1;
    }
    matrix_copy(res, res_tmp);
}

int mat[3][3];
int res[3][3];
int elem[3][3];

void init(int a, int b, int c) {
    mat[0][0] = a;
    mat[0][1] = b;
    mat[0][2] = c;
    mat[1][1] = mat[1][2] = mat[2][0] = mat[2][2] = 0;
    mat[1][0] = mat[2][1] = 1;
}

int main()
{
    in >> t;
    while (t--) {
        int x, y, z, a, b, c, n;
        in >> x >> y >> z >> a >> b >> c >> n;

        init(a, b, c);
        elem[0][0] = z;
        elem[1][0] = y;
        elem[2][0] = x;

        log_power(res, mat, n - 2);

        matrix_mul(res, res, elem, 3, 3, 3, 1);

        out << res[0][0] << "\n";
    }
}