#include <fstream>
#include <iostream>

using namespace std;

ifstream f ("iepuri.in");
ofstream g ("iepuri.out");

const int N = 3;
const int MOD = 666013;

struct Mat {
    int mat[N][N];
} nullMat, initMat;

Mat prod(Mat p, Mat a){
    Mat aux;
    for(int i=0; i<N; i++)
        for(int k=0; k<N; k++){
            
            aux.mat[i][k] = 0;
            for(int j=0; j<N; j++)
                aux.mat[i][k] += (long long)p.mat[i][j] * a.mat[j][k]%MOD;
                aux.mat[i][k] %= MOD;
                
        }
        
    return aux;
            
}

Mat exponentiere(Mat p, int pwr){
    if(pwr == 0)
        return nullMat;
    if(pwr % 2 == 0)
        return exponentiere(prod(p, p), pwr/2);
    return prod(p, exponentiere(prod(p, p), pwr/2));
}

int main()
{
    int t, x, y, z, a, b, c, n;
    f>>t;
    
    for(int u=1; u<=t; u++){
        
        f>>x>>y>>z>>a>>b>>c>>n;
        nullMat = {{{z, 0, 0}, {y, 0, 0}, {x, 0, 0}}};
        initMat = {{{a, b, c}, {1, 0, 0}, {0, 1, 0}}};
        g << exponentiere(initMat, n-2).mat[0][0] << '\n';
        
    }
    
   

    return 0;
}