#include <cstdio>
#include <algorithm>
#define mod 666013

using namespace std;

int n, i, j, a, b, c, x, y ,z, t;
long long v[5][5], xx[5], zz[5], p[5][5];

void mult_v(long long a[5][5], long long b[5][5], long long c[5][5]) {
    int i, j, k;
    memset(c, 0, sizeof(c));
    for (i = 1; i <= 3; i++)
        for (j = 1; j <= 3; j++)
            for (k = 1; k <= 3; k++) {
                c[i][j] += a[i][k] * b[k][j];     
                c[i][j] %= mod;
            }
}

void log(int n, long long x[5][5]) {
    long long t[5][5];
    if (n == 1) {
        memcpy(x, v, sizeof(v));
        return;
    }
        
    if (n % 2 == 0) {
		memset(t, 0, sizeof(t));
        log(n / 2, t);
		memset(x, 0, sizeof(x));
        mult_v(t, t, x);    
    }    
    else {
		memset(t, 0, sizeof(t));		
        log(n - 1, t);
		memset(x, 0, sizeof(x));		
        mult_v(t, v, x);    
    }
}

void mult_x(long long a[5][5], long long b[5], long long c[5]) {
    int i, j, k;   
    memset(c, 0, sizeof(c));
    for (i = 1; i <= 3; i++)
        for (j = 1; j <= 3; j++) {
            c[i] += a[i][j] * b[j];     
            c[i] %= mod;
        }
     
}

int main(){
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    
    scanf("%d", &t);
    
    for(; t > 0; t--) {
        scanf("%d%d%d%d%d%d%d", &xx[3], &xx[2], &xx[1], &x, &y, &z, &n);   
        v[1][1] = x; v[1][2] = y; v[1][3] = z;
        v[2][1] = 1; v[3][2] = 1;
		memset(p, 0, sizeof(p));
        log(n - 2, p); 
		memset(zz, 0, sizeof(zz));
        mult_x(p, xx, zz); 
        printf("%d\n", zz[1]);
    }

    return 0;
}