#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MOD = 666013;
ull A[4][4], B[4][4], copyy[4][4];
void inmultire(ull a[4][4], ull b[4][4]){
    ull mat[4][4];
    memset(mat, 0, sizeof(mat));
    for(int i = 1; i<=3; i++){
        for(int j = 1; j<=3; j++){
            for(int k = 1; k<=3; k++) mat[i][j]+=(a[i][k]*b[k][j])%MOD;
        }
    }
    for(int i = 1; i<=3; i++){
        for(int j = 1; j<=3; j++) a[i][j] = mat[i][j] % MOD;
    }
}
void power(ull k){
    while(k){
        if(k%2==1){
            inmultire(copyy, B);
            k--;
        }
        else{
            inmultire(B, B);
            k/=2;
        }
    }
}
int main(){
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    int t, x, y, z, a, b, c, n;
    scanf("%d", &t);
    for(int i = 1; i<=t; i++){
        scanf("%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &n);
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(copyy, 0, sizeof(B));
        copyy[1][1] = copyy[2][2] = copyy[3][3] = 1;
        A[1][1] = x;
        A[1][2] = y;
        A[1][3] = z;
        B[2][1] = B[3][2] = 1;
        B[1][3] = c;
        B[2][3] = b;
        B[3][3] = a;
        power(n-2);
        inmultire(A, copyy);
        printf("%llu\n", A[1][3] % MOD);
    }
}