#include<fstream>
#include<cstring>
#define dim 666013
using namespace std;
int T, i, j, x, y, z, a, b, c, A[4][4], ri[4][4], C[4][4], n;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
void inmulteste(int C[4][4], int A[4][4], int ri[4][4]){
    for(int i=1; i<=3; i++){
        for(int j=1; j<=3; j++){
            C[i][j]=0;
            for(int k=1; k<=3; k++)
                C[i][j]+=A[i][k]*ri[k][j];
                C[i][j]%=dim;
        }
    }
}
int main(){
    in>>T;
    for(;T--;){
        in>>x>>y>>z>>a>>b>>c>>n;
        for(i=1; i<=3; i++){
            for(j=1; j<=3; j++){
                A[i][j]=0;
                ri[i][j]=0;
            }
        }
        for(i=1; i<=n; i++)
            ri[i][i]=1;
        A[1][2]=1;
        A[2][3]=1;
        A[3][1]=c;
        A[3][2]=b;
        A[3][3]=a;
        n-=2;
        while(n!=0){
            if(n%2==1){
                inmulteste(C, A, ri);
                memcpy(ri, C, sizeof(ri));
            }
            inmulteste(C, A, A);
            memcpy(A, C, sizeof(A));
            n/=2;
        }
        out<<(ri[3][1]*x+ri[3][2]*y+ri[3][3]*z)%dim<<"\n";
    }
return 0;
}