#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 666013;

int n, x, y, z, a, b, c;

void multiply ( int a[3][3], int b[3][3] ) {
    
    int c[3][3];
    
    for ( int i = 0; i < 3; i++ ) {
        for ( int j = 0; j < 3; j++ ) {
            
            c[i][j] = 0;
            
            for (int k = 0; k < 3; k++)
                c[i][j] = ( c[i][j] + a[i][k] * b[k][j] ) % MOD;
        }
    }
    
    for ( int i = 0; i < 3; i++ )
        for ( int j = 0; j < 3; j++ )
            a[i][j] = c[i][j];
}

int power ( int f[3][3], int n ) {
    
    int m[3][3] = { {a, b, c}, {1, 0, 0}, {0, 1, 0} };
    
    if ( n == 1 )
        return ( f[0][0] + f[0][1] ) % MOD;
    
    power ( f, n / 2 );
    
    multiply ( f, f );
    
    if ( n % 2 != 0 )
        multiply ( f, m );
    
   return ( f[0][0] + f[0][1] ) % MOD;
}

int main () {
    
    int t;
    
    cin >> t;
    
    for ( int i = 0; i < t; i++ ) {
        
        cin >> x >> y >> z >> a >> b >> c >> n;
        
        int f[3][3] = { {a, b, c}, {1, 0, 0}, {0, 1, 0} };
        
        power ( f, n - 2 );
        
        cout << ( z * f[0][0] + y * f[0][1] + x * f[0][2] ) % MOD << "\n";
    }
    
    return 0;
}