#include<cstdio>
#include<cstring>
const int mod = 666013;
using namespace std;

int i , j , a , b , c, x , y , z , n , mat[5][5] , rez[5][5] , C[5][5] , t , v[5] , ans[5] , k;

void set_matrix () {
	mat[1][1] = a , mat[2][1] = b , mat[3][1] = c;
	mat[1][2] = 1 , mat[2][2] = 0 , mat[3][2] = 0;
	mat[1][3] = 0 , mat[2][3] = 1 , mat[3][3] = 0;
}

void multiply( int A[5][5] , int B[5][5] ) {
	int i , j , k;
	
	memset(C , 0 , sizeof(C));
	
	for( i = 1 ; i <= 3 ; ++i )
		for( j = 1 ; j <= 3 ; ++j )
			for( k = 1 ; k <= 3 ; ++k )
				C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j] ) % mod; 
	
	for( i = 1 ; i <= 3 ; ++i ) 
		for( j = 1 ; j <= 3 ; ++j ) 
			A[i][j] = C[i][j];
}

void raise_matrix( int n ) {
	
	int i;
	memset(rez , 0 , sizeof(rez));
	for( i = 1 ; i <= 3 ; ++i ) 
		rez[i][i] = 1;
	
	for( i = 0 ; ( 1 << i ) <= n ; ++i ) {
		if ( n & (1 << i) )
			multiply(rez , mat);
		multiply(mat , mat);
	}
}

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