#include <iostream>
#include <stdio.h>
#include <vector>
#define MOD 666013

using namespace std;

template<typename T>
class Matrix {
	public:
		Matrix( int N, int M ) {
			Lines = N;
			Cols = M;
			for ( int i = 0; i < Lines; i++ ) {
				Elements.push_back( vector<T>() );
				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];
			}
		}
		
		void operator=( Matrix A ) {
			for ( int i = 0; i < A.Lines; i++ ) {
				if ( i >= Lines ) Elements.push_back( vector<T>() );
				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("%lld ", Elements[i][j-1] ) );
		}

	vector< vector<T> > Elements;
	int Lines, Cols;
};

long long T,A,B,C,X,Y,Z,N;
vector<long long> St;
long long Start[ 9 ] = { 0, 0, 0, 1, 0, 0, 0, 1, 0 };
long long 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("%lld\n",&T); T; --T ) {
		scanf("%lld%lld%lld%lld%lld%lld%lld\n", &Aux[0], &Aux[1], &Aux[2], &Start[8], &Start[5], &Start[2], &N );
		
		St.clear(); for( int i = 0; i < 9; i++ ) St.push_back( Start[i]%MOD );
		Matrix<long long> Din(3, 3);
		Din.fromVector( St );
		
		St.clear(); for ( int i = 0; i < 3; i++ ) St.push_back( Aux[i] );
		Matrix<long long> Init( 3, 3 );
		Init.fromVector( St );
		
		printf("%lld\n", ( Init*(Din^(N-2)) ).Elements[0][2] );
	}	
	
	return 0;	
}