#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

class Matrix {
	public:
		Matrix( int N, int M ) {
			Lines = N;
			Cols = M;
			MOD = 666013;
			for ( int i = 0; i < Lines; i++ ) {
				Elements.push_back( vector<long long>() );
				for ( int j = 0; j < Cols; j++ )
					Elements[i].push_back( 0 );
			}
		}

		void fromVector( vector< long long > A ) {
			if ( A.size() > ( Lines+1 )*( Cols+1 ) ) return;
			int i = 0, j = 0;
			for ( int k = 0; k < A.size(); k++, j++ ) {
				if ( j == Cols ) { i++; j = 0; } 
				Elements[i][j] = A[k];
			}
		}
		
		bool operator=( Matrix A ) {
			for ( int i = 0; i < A.Lines; i++ ) {
				if ( i >= Lines ) Elements.push_back( vector<long long>() );
				for ( int j = 0; j < A.Cols; j++ ) {
					if ( j >= Cols ) Elements[i].push_back( A.Elements[i][j] );
					else Elements[i][j] = A.Elements[i][j];
				}	
			}
		}
	
		Matrix operator*( Matrix A ) {
			Matrix Result( Lines, A.Cols );
			for ( int k = 0; k < Cols; k++ ) 
				for ( int i = 0; i < Lines; i++ ) 
					for ( int j = 0; j < A.Cols; j++ )
						Result.Elements[i][j] = ( Result.Elements[i][j] + ( Elements[i][k]*A.Elements[k][j]) % MOD ) % MOD;
			return Result;
		} 

		Matrix operator^( int Power ) {
			Matrix Result( Lines, Cols );
			Matrix Cur( Lines, Cols );
			Result.toI();
			Cur = (*this);

			for ( int i = 0; i < 30 && Power; i++ ) {
				if ( (1<<i) & Power ) { Result = Result*Cur; Power -= ( 1<< i ); }
				Cur = Cur*Cur;
			}
			return Result;
		}	

		void toI() {
			for ( int i = 0; i < Lines; i++ ) 
				Elements[i][i] = 1;
		}
		void print() {
			for ( int i = 0; i < Lines; i++, printf("\n") )
				for ( int j = 0; j < Cols; j++, printf("%d ", Elements[i][j-1] ) );
		}

	vector< vector<long long> > Elements;
	int Lines, Cols;
	long long MOD;
};

int T,A,B,C,X,Y,Z,N;
vector<long long> St;
int Start[ 9 ] = { 0, 0, 0, 1, 0, 0, 0, 1, 0 };
int Aux[3];

int main() 
{
#ifndef PC_RUN
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
#else
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
#endif
	
	for ( scanf("%d\n",&T); T; --T ) {
		scanf("%d%d%d%d%d%d%d\n", &Aux[0], &Aux[1], &Aux[2], &A, &B, &C, &N );
		Start[2] =C; Start[5] = B; Start[8] = A;
		St.clear();
		for( int i = 0; i < 9; i++ ) St.push_back( Start[i] );
		Matrix Din(3, 3);
		Din.fromVector( St );
		Din = ( Din^(N-2) );
		St.clear();
		for ( int i = 0; i < 3; i++ ) St.push_back( Aux[i] );
		Matrix Init( 3, 3 );
		Init.fromVector( St );
		printf("%lld\n", ( Init*Din ).Elements[0][2] );
	}	
	
	return 0;	
}