# include <cstdio>
# include <string>

using namespace std;

# define FIN "iepuri.in"
# define FOUT "iepuri.out"
# define MOD 666013
# define MAX_N 4

long long Mat[MAX_N][MAX_N];
long long Sol[MAX_N][MAX_N];
long long aux[MAX_N][MAX_N];
int A, B, C, X, Y, Z, T, N, i, j, k;

    int main() {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);
        
        scanf("%d", &T);
        for (; T; --T) {
            scanf("%d%d%d%d%d%d%d", &X, &Y, &Z, &A, &B, &C, &N);
            
            memset(Mat, 0, sizeof(Mat));
            memset(Sol, 0, sizeof(Sol));
            
            Sol[1][1] = Sol[2][2] = Sol[3][3] = 1;
            Mat[2][1] = Mat[3][2] = 1;
            Mat[1][3] = C; Mat[2][3] = B; Mat[3][3] = A;
            
            int Bnd;
            for (Bnd = 0; (1 << Bnd) <= (N - 2) >> 1; ++Bnd);
            
            for (int bit = 0; bit <= Bnd; ++bit) {
                if ((N - 2) & (1 << bit)) {
                    memset(aux, 0, sizeof(aux));
                    for (i = 1; i < MAX_N; ++i)
                       for (j = 1; j < MAX_N; ++j)
                          for (k = 1; k < MAX_N; ++k)
                             aux[i][j] = (aux[i][j] + Sol[i][k] * Mat[k][j]) % MOD;
                    for (i = 1; i < MAX_N; ++i)
                       for (j = 1; j < MAX_N; ++j) Sol[i][j] = aux[i][j];
                }
                
                memset(aux, 0, sizeof(aux));
                for (i = 1; i < MAX_N; ++i)
                   for (j = 1; j < MAX_N; ++j)
                      for (k = 1; k < MAX_N; ++k)
                         aux[i][j] = (aux[i][j] + Mat[i][k] * Mat[k][j]) % MOD;
                for (i = 1; i < MAX_N; ++i)
                   for (j = 1; j < MAX_N; ++j) Mat[i][j] = aux[i][j];
            }
            
            long long Rez;
            
            Rez = (((X * Sol[1][3]) % MOD + Y * Sol[2][3])% MOD + Z * Sol[3][3]) % MOD;
            
            printf("%lld\n", Rez);
        }
        
        return 0;
    }