#include<stdio.h>   
#define infile "iepuri.in"   
#define outfile "iepuri.out"   
#define modulo 666013   
long long z[1][3]; //nr-ul de iepuri din ultimele 3 zile   
long long x[3][3]; //matricea cu care inmultim   
  
void inmultire(long long a[3][3], long long b[3][3], long long c[3][3], int x, int y)   
    {   
    long long d[3][3];   
    int i,j,k;   
    for(i=0;i<x;i++) //linia   
        for(j=0;j<y;j++) //coloana   
            {   
            d[i][j]=0;   
            for(k=0;k<y;k++)   
                d[i][j]=(d[i][j]+a[i][k]*b[k][j])%modulo;   
            }   
    for(i=0;i<x;i++)   
        for(j=0;j<y;j++)   
            c[i][j]=d[i][j]; //punem in c   
    }   
  
int ridica_putere(int p)   
    {   
    while(p) //trebuie sa ridicam la puterea p   
        {   
        if(p%2) inmultire(z,x,z,1,3); //z=z*x   
        inmultire(x,x,x,3,3); //x=x^2   
        p/=2;   
        }   
    return z[0][2];   
    }   
  
int main()   
{   
int t,n;   
freopen(infile,"r",stdin);   
freopen(outfile,"w",stdout);   
  
  
scanf("%d\n",&t); //numarul de teste   
while(t--) //testam   
    {   
    x[1][0]=x[2][1]=1; //cele doua pozitii cu 1 din matricea principala   
    x[0][0]=x[0][1]=x[1][1]=x[2][0]=0; //pozitiile cu 0   
    scanf("%lld %lld %lld",&z[0][0],&z[0][1],&z[0][2]);   
    scanf("%lld %lld %lld",&x[2][2],&x[1][2],&x[0][2]); //cele 3 valori de multiplicare   
    scanf("%d",&n); //ziua la care trebuie sa aflam numarul de iepuri   
    printf("%d\n",ridica_putere(n-2));   
    }   
  
  
fclose(stdin);   
fclose(stdout);   
return 0;   
}