# include <stdio.h>
# include <cstring>

# define input "iepuri.in"
# define output "iepuri.out"

# define max 666014
# define div 666013

long i, j, k, n, x, y, z, a, b, c, aux, T;
long v[3][3];
long t[3][3];

void inmulteste(long p[3][3],long f1[3][3],long f2[3][3])
{
    int i,j,k;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {
            p[i][j] = 0;
            for(k=0;k<3;k++)
            {
                p[i][j] += (f1[i][k] * f2[k][j]);
                p[i][j] %= div;
            }
        }
}

void prod(long n)
{
    while(n)
    {
       long r[3][3];
       if(n%2)
       {
          inmulteste(r,t,v); 
          memcpy(t,r,sizeof(t));
       }
       inmulteste(r,v,v);
       memcpy(v,r,sizeof(v));
       n>>=1;
    }
}

int main()
{
    freopen(input, "r", stdin);
    freopen( output, "w", stdout);
    scanf("%ld",&T);
    
    while(T--)
    {        
        scanf("%ld%ld%ld%ld%ld%ld%ld",&x,&y,&z,&a,&b,&c,&n);
        
        for(i=3;i<=n;i++)
        {
            long aux ;
            aux = c*x + b*y + a * z;
            x = y;
            y = z;
            z = aux%div;
        }
        printf("%ld\n",z);
        
       /* v[0][0] = a; v[0][1] = b; v[0][2] = c;
        v[1][0] = 1; v[1][1] = 0; v[1][2] = 0;
        v[2][0] = 0; v[2][1] = 1; v[2][2] = 0;
        
        t[0][0] = 1; t[0][1] = 0; t[0][2] = 0;
        t[1][0] = 0; t[1][1] = 1; t[1][2] = 0;
        t[2][0] = 0; t[2][1] = 0; t[2][2] = 1;
        

        prod(n-2);        
        long res = (t[0][0] * z + t[0][1] * y + t[0][2] * x)%div;*/

//        printf("%ld\n",res);
    }
    
    return 0;    
}