#include <stdio.h>
#define prim 666013

int t, x, y, z, a, b, c, n;
int mat[3][3], curent[3][3], aux[3][3];
int v[50];

void init_mat() {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            mat[i][j] = 0;
    mat[0][0] = a % prim; mat[0][1] = b % prim; mat[0][2] = c % prim;
    mat[1][0] = 1; mat[2][1] = 1;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			curent[i][j] = mat[i][j];
}

void init_put() {
    int k = n; v[0] = 0;
    while (k > 0) {
          v[++v[0]] = k;
          k /= 2;
    }
      
    for (int i = 1; i <= v[0] / 2; i++) {
        int aux = v[i];
        v[i] = v[v[0] + 1 - i];
        v[v[0] + 1 - i] = aux;
    }     
}

void aux_zero() {
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			aux[i][j] = 0;
}

void inmultire_curenta() {
    aux_zero();
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
			aux[i][j] = 0;
			for (int k = 0; k < 3; k++)
                aux[i][j] = (aux[i][j] + curent[i][k] * curent[k][j]) % prim;
		}
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            curent[i][j] = aux[i][j];
}

void inmultire_initiala() {
    aux_zero();
	for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                aux[i][j] = (aux[i][j] + curent[i][k] * mat[k][j]) % prim;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            curent[i][j] = aux[i][j];
}

void inm_log(int k) {
    if (k >= v[0]) return;
     
    inmultire_curenta();
    if (v[k + 1] % 2 == 1) inmultire_initiala();
	
	inm_log(k + 1);
}

void write() {
    int sol = 0;
    sol = (sol + z * curent[0][0]) % prim;
	sol = (sol + y * curent[0][1]) % prim;
	sol = (sol + x * curent[0][2]) % prim;
	
    printf("%d\n", sol);
}

int main() {

    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);

    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d %d %d %d %d", &x, &y, &z, &a, &b, &c, &n);
		n -= 2;
		
        init_mat();
        init_put();
        inm_log(1);
    
        write();
    }
    
    
    return 0;
}