#include <stdio.h>
#define ORD 4 //(de fapt e 3)
#define MOD 666013
FILE *f, *g;

int a, b, c;
int x, y, z;
int n;
int t;

int rez[2][ORD];
int crez[2][ORD];
int baza[ORD][ORD];
int cbaza[ORD][ORD];

void citire();
int calcul();
inline void init();

int main()
{
    f = fopen("iepuri.in", "r");
    g = fopen("iepuri.out", "w");

    int r;

    fscanf(f, "%d", &t);

    for (int i = 1; i <= t; ++i){
        citire();
        init();
        r = calcul();
        fprintf(g, "%d\n", r);
    }

    fclose(f);
    fclose(g);

    return 0;
}

void citire(){
    fscanf(f, "%d%d%d", &x, &y, &z);
    fscanf(f, "%d%d%d", &a, &b, &c);
    fscanf(f, "%d", &n);
}

int calcul(){
    //n--;
    int i, j, k;

    while (n > 0){
        if (n%2 == 0){
            for (i = 1; i < ORD; ++i)
                for (j = 1; j < ORD; ++j){
                    cbaza[i][j] = 0;
                    for (k = 1; k < ORD; ++k)
                       cbaza[i][j] += ((baza[i][k] * baza[k][j])%MOD);
                }

            for (i = 1; i < ORD; ++i)
                for (j = 1; j < ORD; ++j)
                    baza[i][j] = cbaza[i][j];

            n /= 2;
        }else{
            for (j = 1; j < ORD; ++j){
                crez[1][j] = 0;
                for (k = 1; k < ORD; ++k)
                   crez[1][j] += ((rez[1][k] * baza[k][j])%MOD);
            }

            for (j = 1; j < ORD; ++j)
                rez[1][j] = crez[1][j];

            n--;
        }
    }
    return rez[1][1];
}

inline void init(){
    rez[1][1] = x;
    rez[1][2] = y;
    rez[1][3] = z;

    baza[1][1] = baza[1][2] = baza[2][2] = baza[3][1] = 0;
    baza[2][1] = baza[3][2] = 1;

    baza[1][3] = c;
    baza[2][3] = b;
    baza[3][3] = a;
}