#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long lint;

#define MODULO 666013

lint dumb_solve(lint x, lint y, lint z, lint a, lint b, lint c, int n)
{
    int q;
    while (n > 2) {
        q = (a * z + b * y + c * x) % MODULO;
        x = y;
        y = z;
        z = q;
        --n;
    }
    return z;
}

lint solve(lint x, lint y, lint z, lint a, lint b, lint c, int n)
{
    lint mat[3][3], nmat[3][3];
    lint vec[3], nvec[3];
    int m = n / 3;
    int i, j;

    vec[0] = x;
    vec[1] = y;
    vec[2] = z;

    mat[0][0] = c;
    mat[0][1] = b;
    mat[0][2] = a;
    mat[1][0] = (a * mat[0][0]) % MODULO;
    mat[1][1] = (a * mat[0][1] + c) % MODULO;
    mat[1][2] = (a * mat[0][2] + b) % MODULO;
    mat[2][0] = (a * mat[1][0] + b * mat[0][0]) % MODULO;
    mat[2][1] = (a * mat[1][1] + b * mat[0][1]) % MODULO;
    mat[2][2] = (a * mat[1][2] + b * mat[0][2] + c) % MODULO;

    while (m) {
        if (m % 2) {
            nvec[0] = (vec[0] * mat[0][0] + vec[1] * mat[0][1] + vec[2] * mat[0][2]) % MODULO;
            nvec[1] = (vec[0] * mat[1][0] + vec[1] * mat[1][1] + vec[2] * mat[1][2]) % MODULO;
            nvec[2] = (vec[0] * mat[2][0] + vec[1] * mat[2][1] + vec[2] * mat[2][2]) % MODULO;
            memcpy(vec, nvec, sizeof(vec));
        }
        for (i = 0; i < 3; ++i) {
            for (j = 0; j < 3; ++j) {
                nmat[i][j] = (mat[i][0] * mat[0][j] + mat[i][1] * mat[1][j] + mat[i][2] * mat[2][j]) % MODULO;
            }
        }
        memcpy(mat, nmat, sizeof(mat));
        m /= 2;
    }
    return vec[n % 3];
}

void test(int t)
{
    int x, y, z, a, b, c, n;
    lint r1, r2;
    while (t--) {
        x = rand() % 10000 + 1;
        y = rand() % 10000 + 1;
        z = rand() % 10000 + 1;
        a = rand() % 1000 + 1;
        b = rand() % 1000 + 1;
        c = rand() % 1000 + 1;
        n = rand() % 1000 + 3;
        r2 = solve(x, y, z, a, b, c, n);
        r1 = dumb_solve(x, y, z, a, b, c, n);
        if (r1 != r2) {
            printf("%d %d %d  %d %d %d  %d: %lld != %lld\n", x, y, z, a, b, c, n, r1, r2);
            printf("ABORT");
            abort();
        } else {
            printf("%d %d %d  %d %d %d  %d: %lld == %lld\n", x, y, z, a, b, c, n, r1, r2);
        }
    }
}

int main(void)
{
    int t;
    int x, y, z, a, b, c, n;
    freopen("iepuri.in", "rt", stdin);
    freopen("iepuri.out", "wt", stdout);
    scanf("%d", &t);
//    test(1000);
    while (t--) {
        scanf("%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n);
        printf("%lld\n", solve(x, y, z, a, b, c, n));
    }
    return 0;
}