#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

#define modulo 666013

char FileIn[] =  { "iepuri.in" };
char FileOut[] = { "iepuri.out" };

typedef int MATRIX[4][4];

int a[4], b[4];

MATRIX A, B, AUX, RES, SOL;

int N, T;

void init(){

    for ( int i = 1; i <= 3; i++ )
        A[i][1] = a[i];

    for ( int i = 1; i < 3; i++ )
        B[i][i + 1] = 1;

    for ( int i = 1; i <= 3; i++ )
        B[3][i] = b[i];
}

void inmultire( MATRIX a, MATRIX b, MATRIX c ){

    for ( int i = 1; i <= 3; ++i )
        for ( int j = 1; j <= 3; ++j )
            for ( int l = 1; l <= 3; ++l )
                c[i][j] = ( c[i][j] + 1LL * a[i][l] * b[l][j] ) % modulo;
}

void Fast_Exponentiation(){

    for ( int i = 1; i <= 3; i++ )
        RES[i][i] = 1;

    while ( N ){

        //int rest = impartire( N, 2 );

        if ( N & 1 ){

            memset( AUX, 0, sizeof( AUX ) );
            inmultire( RES, B, AUX );
            memcpy( RES, AUX, sizeof( AUX ) );
        }

        N >>= 1;

        memset( AUX, 0, sizeof( AUX ) );
        inmultire( B, B, AUX );
        memcpy( B, AUX, sizeof( AUX ) );

    }

    memcpy( B, RES, sizeof( RES ) );
}

void final(){

    for ( int c = 1; c <= 3; c++ ){

        int sum = 0;

        for ( int l = 1; l <= 3; l++ )
            sum = ( sum + B[c][l] * A[l][1] ) % modulo;

        SOL[c][1] = sum;
    }
}

void sterge(){

    memset( A, 0, sizeof( A ) );
    memset( B, 0, sizeof( B ) );
    memset( AUX, 0, sizeof( AUX ) );
    memset( RES, 0, sizeof( RES ) );
    memset( SOL, 0, sizeof( SOL ) );

}

void rezolva(){

    ifstream f(FileIn);
    ofstream g(FileOut);

    f >> T;

    for ( ; T; T-- ){

        sterge();

        f >> a[1] >> a[2] >> a[3];
        f >> b[1] >> b[2] >> b[3];
        f >> N;

        N -= 3;

        init();
        Fast_Exponentiation();
        final();

        g << SOL[3][1] << "\n";
    }

    //g.close();
}

int main(){

    rezolva();

    return 0;
}