#include <bits/stdc++.h>
#define int long long
#define MOD 666013
using namespace std;
int  a[4][4], b[4][4], c[4][4];
void inmul(int  e[4][4], int  f[4][4]) {
    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] += ((e[i][k] % MOD) * (f[k][j] % MOD)) % MOD;
    for (i = 1; i <= 3; i++)
        for (j = 1; j <= 3; j++)
            f[i][j] = c[i][j] % MOD;
}
int32_t main() {
    ifstream cin("iepuri.in");
    ofstream cout("iepuri.out");
    int t, l;
    cin >> t;
    if (t > 50) return 0;
    for (int l = 1; l <= t; l++) {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        cin >> b[3][1] >> b[2][1] >> b[1][1] >> a[1][1] >> a[1][2] >> a[1][3];
        int n;
        cin >> n;
        n -= 2;
        a[2][1] = 1;
        a[3][2] = 1;
        int  p;
        for(p=n; p; p=p>>1) {
            if(p&1)inmul(a,b);
            inmul(a,a);
        }
        cout<<b[1][1]<<"\n";
    }
    return 0;
}