#include<stdio.h>
#define mod 666013
long long  k,a[4][4],rez[4][4],a1[4][4],rez1[4][4];
void calc (int s, int c , int l, int p, int m , int n){
    int i,j;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++){
            rez[i][j]=0;
            rez1[i][j]=0;
            a[i][j]=0;
            a1[i][j]=0;
        }
    a[1][1]=a[1][2]=a[2][2]=a[3][1]=0;
    a[2][1]=a[3][2]=1;
    a[1][3]=n;
    a[2][3]=m;
    a[3][3]=p;
    rez[1][1]=rez[2][2]=rez[3][3]=1;
    k=k-2;
    while(k!=0){
        if(k%2==1){
            k--;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    rez1[i][j]=rez[i][j];
            rez[1][1]=((rez1[1][1]*a[1][1])%mod+(rez1[1][2]*a[2][1])%mod+(rez1[1][3]*a[3][1])%mod)%mod;
            rez[1][2]=((rez1[1][1]*a[1][2])%mod+(rez1[1][2]*a[2][2])%mod+(rez1[1][3]*a[3][2])%mod)%mod;
            rez[1][3]=((rez1[1][1]*a[1][3])%mod+(rez1[1][2]*a[2][3])%mod+(rez1[1][3]*a[3][3])%mod)%mod;
            rez[2][1]=((rez1[2][1]*a[1][1])%mod+(rez1[2][2]*a[2][1])%mod+(rez1[2][3]*a[3][1])%mod)%mod;
            rez[2][2]=((rez1[2][1]*a[1][2])%mod+(rez1[2][2]*a[2][2])%mod+(rez1[2][3]*a[3][2])%mod)%mod;
            rez[2][3]=((rez1[2][1]*a[1][3])%mod+(rez1[2][2]*a[2][3])%mod+(rez1[2][3]*a[3][3])%mod)%mod;
            rez[3][1]=((rez1[3][1]*a[1][1])%mod+(rez1[3][2]*a[2][1])%mod+(rez1[3][3]*a[3][1])%mod)%mod;
            rez[3][2]=((rez1[3][1]*a[1][2])%mod+(rez1[3][2]*a[2][2])%mod+(rez1[3][3]*a[3][2])%mod)%mod;
            rez[3][3]=((rez1[3][1]*a[1][3])%mod+(rez1[3][2]*a[2][3])%mod+(rez1[3][3]*a[3][3])%mod)%mod;
        }
        else{
            k=k/2;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    a1[i][j]=a[i][j];
            a[1][1]=((a1[1][1]*a1[1][1])%mod+(a1[1][2]*a1[2][1])%mod+(a1[1][3]*a1[3][1])%mod)%mod;
            a[1][2]=((a1[1][1]*a1[1][2])%mod+(a1[1][2]*a1[2][2])%mod+(a1[1][3]*a1[3][2])%mod)%mod;
            a[1][3]=((a1[1][1]*a1[1][3])%mod+(a1[1][2]*a1[2][3])%mod+(a1[1][3]*a1[3][3])%mod)%mod;
            a[2][1]=((a1[2][1]*a1[1][1])%mod+(a1[2][2]*a1[2][1])%mod+(a1[2][3]*a1[3][1])%mod)%mod;
            a[2][2]=((a1[2][1]*a1[1][2])%mod+(a1[2][2]*a1[2][2])%mod+(a1[2][3]*a1[3][2])%mod)%mod;
            a[2][3]=((a1[2][1]*a1[1][3])%mod+(a1[2][2]*a1[2][3])%mod+(a1[2][3]*a1[3][3])%mod)%mod;
            a[3][1]=((a1[3][1]*a1[1][1])%mod+(a1[3][2]*a1[2][1])%mod+(a1[3][3]*a1[3][1])%mod)%mod;
            a[3][2]=((a1[3][1]*a1[1][2])%mod+(a1[3][2]*a1[2][2])%mod+(a1[3][3]*a1[3][2])%mod)%mod;
            a[3][3]=((a1[3][1]*a1[1][3])%mod+(a1[3][2]*a1[2][3])%mod+(a1[3][3]*a1[3][3])%mod)%mod;

        }
    }
    printf("%lld\n",((rez[1][3]*s)%mod+(rez[2][3]*c)%mod+(rez[3][3]*l)%mod)%mod);
}
int main(){
    int t,i,x,y,z,a,b,c;
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;i++){
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&k);
        calc(x,y,z,a,b,c);
    }
    return 0;
}