#include <fstream>
#define MOD 666013
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
long long k, n, t, x, y, z, q, r, s;
long long b[3][3];
void inmultire(long long a[3][3], long long b[3][3], long long c[3][3]){
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            c[i][j]=0;
            for(int l=0;l<=2;l++){
                c[i][j]=(c[i][j]+a[i][l]*b[l][j])%MOD;
            }
        }
    }
}
void copiere(long long a[3][3], long long b[3][3]){
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++)
            a[i][j]=b[i][j];
    }
}
int main() {
    cin>>t;
    while(t--){
        cin>>x>>y>>z>>q>>r>>s>>k;
        long long w[3]={x, y, z};
        if(k<=2){
            cout<<w[k]<<"\n";
            continue;
        }
        long long p[3][3]={{1,0, 0},
                           {0,1, 0},
                           {0, 0, 1}};
        long long a[3][3]={{q, r, s},
                           {1,0, 0},
                           {0, 1, 0}};
        n=k-2;
        while(n){
            if(n%2){
                inmultire(p, a, b);
                copiere(p, b);
            }
            inmultire(a, a, b);

            copiere(a, b);
            n/=2;
        }
        cout<<(z*p[0][0]+y*p[0][1]+x*p[0][2])%MOD<<"\n";
    }
    return 0;
}