#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std;

#define MOD 666013

int t, n, x, y, z, i;
int a[ 4 ][ 4 ];
int b[ 4 ][ 4 ];
int v[ 64 ];

void prd( int a[ 4 ][ 4 ], int b[ 4 ][ 4 ] ) {
    int c[ 4 ][ 4 ];
    memset( c, 0, sizeof( c ) );
    for( int k = 1; k <= 3; ++k )
        for( int i = 1; i <= 3; ++i )
            for( int j = 1; j <= 3; ++j )
                c[ k ][ i ] = ( c[ k ][ i ] + (long long)a[ k ][ j ] * b[ j ][ i ] ) % MOD;
    memcpy( a, c, sizeof( c ) ); 
}


int main()
{   
    ifstream in( "iepuri.in" );
    freopen( "iepuri.out", "w", stdout );

    for( in >> t; t; --t ) {
        memset( a, 0, sizeof( a ) );

        in >> x >> y >> z >> a[ 1 ][ 1 ] >> a[ 1 ][ 2 ] >> a[ 1 ][ 3 ] >> n;
        
        a[ 2 ][ 1 ] = a[ 3 ][ 2 ] = 1;
        n -= 2;

        memcpy( b, a, sizeof( a ) );
        for( i = 0; n; n >>= 1 )
            v[ ++i ] = n % 2;

        for( --i; i; --i ) {
            prd( a, a );
            if( v[ i ] )
                prd( a, b );   
        }
        printf( "%lld\n", ( (long long)z * a[ 1 ][ 1 ] % MOD + (long long)y * a[ 1 ][ 2 ] % MOD + (long long)x * a[ 1 ][ 3 ] ) % MOD );
    }
    
    return 0;
}