#include<cstdlib>
#include<string>
#define lval 666013

int t,a,b,c,x,y,z;
long long n,auxn;
long long m[23][4][4],mp[4][4],maux[4][4];
long long aux1,aux2,aux3;
int i,j,k,l;

void preprocess(){
m[0][1][1]=0;m[0][1][2]=1;m[0][1][3]=0;
m[0][2][1]=0;m[0][2][2]=0;m[0][2][3]=1;
m[0][3][1]=c;m[0][3][2]=b;m[0][3][3]=a;

mp[1][1]=1;mp[1][2]=0;mp[1][3]=0;
mp[2][1]=0;mp[2][2]=1;mp[2][3]=0;
mp[3][1]=0;mp[3][2]=0;mp[3][3]=1;                   


for(i=1;i<=21;i++)
    for(j=1;j<=3;j++)
        for(k=1;k<=3;k++)
            {
            aux1=(m[i-1][j][1]*m[i-1][1][k])%lval;
            aux2=(m[i-1][j][2]*m[i-1][2][k])%lval;
            aux3=(m[i-1][j][3]*m[i-1][3][k])%lval;
            m[i][j][k]=(aux1+aux2+aux3)%lval;
            }                                       
}

int main(){
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);

scanf("%d",&t);

for(k=0;k<t;k++)
{
scanf("%d %d %d %d %d %d %lld",&x,&y,&z,&a,&b,&c,&n);
preprocess();
auxn=n;
i=21;
while(auxn&&i>-1)
    {
    if(1<<i>n)
        i--;
    else    
        {
        auxn-=1<<i;
        for(j=1;j<=3;j++)
            for(k=1;k<=3;k++)
            {
            aux1=(mp[j][1]*m[i][1][k])%lval;
            aux2=(mp[j][2]*m[i][2][k])%lval;
            aux3=(mp[j][3]*m[i][3][k])%lval;
            maux[j][k]=(aux1+aux2+aux3)%lval;
            }
        mp[1][1]=maux[1][1];mp[1][2]=maux[1][2];mp[1][3]=maux[1][3];
        mp[2][1]=maux[2][1];mp[2][2]=maux[2][2];mp[2][3]=maux[2][3];
        mp[3][1]=maux[3][1];mp[3][2]=maux[3][2];mp[3][3]=maux[3][3];
        }
    }

aux1=(x*mp[1][1])%lval;
aux2=(y*mp[1][2])%lval;
aux3=(z*mp[1][3])%lval;
aux1=(aux1+aux2+aux3)%lval;   
printf("%lld\n",aux1);
}

return 0;    
}