#include <fstream>

#define mod 666013

using namespace std;

ifstream fin ( "iepuri.in" );
ofstream fout ( "iepuri.out" );

typedef struct {
    long long m[3][3];
} matrix;

matrix Z;

matrix multiply ( matrix a, matrix b ) {

    matrix res;
    for ( int i = 0; i < 3; i++ )
        for ( int j = 0; j < 3; j++ ) {
            res.m[i][j] = 0;
            for ( int k = 0; k < 3; k++ ) {
                res.m[i][j] += ( a.m[i][k] * b.m[k][j] );
                res.m[i][j] %= mod;
            }
        }

    return res;
}

matrix lgput ( int pow ) {

    if ( pow == 1 )
        return Z;

    matrix temp = lgput ( pow/2 );
    matrix res = multiply( temp, temp );
    if ( pow % 2 != 0 )
        res = multiply ( res, Z );

    return res;
}

void initZ ( int a, int b, int c ) {

    Z.m[0][0] = a; Z.m[1][0] = b; Z.m[2][0] = c;
    Z.m[0][1] = 1;
    Z.m[1][2] = 1;
}

void solve () {

    int n, A, B, C, x, y, z;
    fin >> x >> y >> z >> A >> B >> C >> n;

    initZ( A, B, C );

    matrix M;
    M.m[0][0] = z; M.m[0][1] = y; M.m[0][2] = x;
    for (int i = 1; i < 3; i++)
        for (int j = 0; j < 3; j++)
            M.m[i][j] = 0;

    matrix aux = lgput ( n-2 );
    M = multiply ( M, aux );

    fout << M.m[0][0] << "\n";
}

int main()
{
    int t;
    fin >> t;
    while ( t-- ) {
        solve ();
    }
    return 0;
}