#include<fstream>
#include<cstring>
#define dim 666013
using namespace std;
long long 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(long long C[4][4], long long ri[4][4], long long A[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]+=((ri[i][k]%dim)*(A[k][j]%dim))%dim;
                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<=3; 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, ri, A);
                memcpy(ri, C, sizeof(ri));
            }
            inmulteste(C, A, A);
            memcpy(A, C, sizeof(A));
            n/=2;
        }
        out<<((ri[3][1]*x)%dim+(ri[3][2]*y)%dim+(ri[3][3]*z)%dim)%dim<<"\n";
    }
return 0;
}