#include<bits/stdc++.h>
#define N 5
#define MOD 666013
#define ll long long
using namespace std;

int p,z,y,x,t;
int M[5][5], a[5][5];
int c[N][N];

void mult(int a[N][N], int b[N][N], int n) {
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            ll s=0;
            for (int k=1; k<=n; ++k) s+=(1LL*a[i][k])*(1LL*b[k][j]);
            c[i][j]=s%MOD;
        }
    }
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j) a[i][j]=c[i][j];
}

int main() {
    ifstream cin("iepuri.in");
    ofstream cout("iepuri.out");
    cin>>t;
    while (t--) {
        int x, y; cin>>x>>y>>z;
        for (int i=1; i<=3; ++i)
            for (int j=1; j<=3; ++j) M[i][j]=a[i][j]=0;

        a[1][1]=a[2][2]=a[3][3]=1;
        cin>>M[1][1]>>M[1][2]>>M[1][3];
        M[2][1]=M[3][2]=1;
        cin>>p; p-=2;
        for (int i=0; (1LL<<i)<=p; ++i) {
            if ((1LL<<i) & p) mult(a,M,3);
            mult(M,M,3);
        }
        cout<<(1LL*a[1][1]*z+a[1][2]*y+a[1][3]*x)%MOD<<'\n';
    }
    return 0;
}