#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <new>
#include <fstream>

using namespace std;

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

const long long mod = 666013 ;

void umple(long long **d ,long long a ,long long  b , long long c){
    d[0][0] = a ; d[0][1] = b ; d[0][2] = c;
    d[1][0] = 1 ; d[2][1] = 1 ;
    d[1][1] = 0 ; d[1][2] = 0 ; d[2][0] = 0 ; d[2][2] = 0 ;
}

long long** inmulteste(long long **a , long long **b){
    long long **m = new long long *[4] ;
    for(int i = 0 ; i < 3 ; i ++){
        m[i] = new long long[4] ;
    }
    m[0][0] = ((a[0][0] * b[0][0])%mod + (a[0][1] * b[1][0])%mod + (a[0][2] * b[2][0])%mod) % mod ;
    m[0][1] = ((a[0][0] * b[0][1])%mod + (a[0][1] * b[1][1])%mod + (a[0][2] * b[2][1])%mod) % mod ;
    m[0][2] = ((a[0][0] * b[0][2])%mod + (a[0][1] * b[1][2])%mod + (a[0][2] * b[2][2])%mod) % mod ;
    m[1][0] = ((a[1][0] * b[0][0])%mod + (a[1][1] * b[1][0])%mod + (a[1][2] * b[2][0])%mod) % mod ;
    m[1][1] = ((a[1][0] * b[0][1])%mod + (a[1][1] * b[1][1])%mod + (a[1][2] * b[2][1])%mod) % mod ;
    m[1][2] = ((a[1][0] * b[0][2])%mod + (a[1][1] * b[1][2])%mod + (a[1][2] * b[2][2])%mod) % mod ;
    m[2][0] = ((a[2][0] * b[0][0])%mod + (a[2][1] * b[1][0])%mod + (a[2][2] * b[2][0])%mod) % mod ;
    m[2][1] = ((a[2][0] * b[0][1])%mod + (a[2][1] * b[1][1])%mod + (a[2][2] * b[2][1])%mod) % mod ;
    m[2][2] = ((a[2][0] * b[0][2])%mod + (a[2][1] * b[1][2])%mod + (a[2][2] * b[2][2])%mod) % mod ;
    return m ; 
}

long long** putere(long long n , long long **d){
    long long **put = new long long *[4] ;
    for(int i = 0 ; i < 3 ; i ++){
        put[i] = new long long[4] ;
    }
    for(int i = 0 ; i < 3 ; i ++){
        put[i][i] = 1 ;
    }
    while(n){
        if(n & 1){
            put = inmulteste(put , d) ;
        }
        d = inmulteste(d , d) ;
        n /= 2 ;
    }
    return put ;
}

long long sol(long long **d , long long x , long long y , long long z){
    return ((d[0][0] * z % mod) % mod + (d[0][1] * y % mod) % mod + (d[0][2] * x % mod) % mod) % mod ;
}

int main() {
    long long t ;
    fin >> t ;
    long long **d = new long long *[4] ;
    for(int i = 0 ; i < 3 ; i ++){
        d[i] = new long long[4] ;
    }
    for(  ; t != 0 ; t --){
        long long n , x, y , z , a , b , c;
       	fin  >> x >> y >> z >> a >> b >> c >> n ;
        umple(d , a , b , c) ;
        if(n == 0){
            fout << x << "\n" ;
        }
        if(n == 1){
            fout << y  << "\n" ;
        }
	if(n == 2){
	    fout << z << "\n" ;
	}
        if(n != 2 && n != 1 && n != 0){
            d = putere(n - 2 , d) ;
            fout << sol(d , x , y , z) << "\n" ;
        } 
    }
    fin.close() ;
    fout.close() ;
    return 0;
}