#include <stdio.h>
#include <stdlib.h>
int i,j,t,x,y,z,a,b,c,n,X[7][7],Y[7][7];
long long f[7][7];

void mult(int X[7][7], int Y[7][7]){
    int i,j,k;
    for( i = 1 ; i <= 3 ; i++ ){
        for( j = 1 ; j <= 3 ; j++ ){
            f[i][j] = 0;
            for( k = 1 ; k <= 3 ; k++ ){
                f[i][j] = ( 0LL + f[i][j] + 1LL * X[i][k] * Y[k][j] ) % 666013;
            }
        }
    }
    for( i = 1 ; i <= 3 ; i++ ){
        for ( j = 1 ; j <= 3 ; j++ ){
            X[i][j]=f[i][j];
        }
    }
}
int main(){
    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, &n);
        n = n - 2;
        X[1][1] = x;
        X[1][2] = y;
        X[1][3] = z;
        Y[3][3] = a;
        Y[2][3] = b;
        Y[1][3] = c;
        Y[1][1] = Y[1][2] = Y[2][2] = Y[3][1] = 0;
        Y[2][1] = Y[3][2]=1;
        while( n > 0 ){
            if( n % 2 == 1 ){
                mult( X , Y );
                mult( Y , Y );
            }
            else
                mult( Y , Y );
            n = n / 2;
        }
        printf( "%d\n" , X[1][3] );
    }
    return 0;
}