#include <bits/stdc++.h>
using namespace std;

#define ll long long

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

const int MAXN = 10;
const int INF = 1e8;
const int MOD = 666013;

ll mat1[MAXN][MAXN], mat2[MAXN][MAXN], matf[MAXN][MAXN];
ll finish[MAXN][MAXN];

void inmultire(ll m1[][MAXN], int dx1, int dy1, ll m2[][MAXN], int dx2, int dy2, ll matf[][MAXN]){

    for(int i = 1; i <= dx1; ++i){
        for(int j = 1; j <= dy2; ++j){
            for(int k = 1; k <= dy1; ++ k){
                matf[i][j] += m1[i][k] * m2[k][j];
                matf[i][j] %= MOD;
            }
        }
    }

}

void copiere(ll m2[][MAXN], ll m1[][MAXN], int dx1, int dy1){

    for(int i = 1; i <= dx1; ++i){
        for(int j = 1; j <= dy1; ++j){
            m1[i][j] = m2[i][j], m2[i][j] = 0;
            m1[i][j] %= MOD;
        }
    }

}

void ridicare(ll m1[][MAXN], int dx1, int dy1, int dx2, int dy2, ll power){

    while(power){

        if(power % 2 == 1){
            power--;
            inmultire(m1, dx1, dy1, matf, dx2, dy2, finish);
            copiere(finish, matf, dx1, dy1);
        }

        inmultire(m1, dx1, dy1, m1, dx1, dy1, finish);
        copiere(finish, m1, dx1, dy1);
        power /= 2;

    }

}

void afis(ll matrix[][MAXN], int dx1, int dy1){

    for(int i = 1; i <= dx1; ++i){
        for(int j = 1; j <= dy1; ++j){

            fout << matrix[i][j] << " " ;

        }
        fout << '\n';
    }
}

void initializare(){
    for(int i = 1; i <= 3; ++i){
        for(int j = 1; j <= 3; ++j){
            matf[i][j] = 0;
            matf[i][i] = 1;
            mat1[i][j] = 0;
            mat2[1][j] = 0;
            finish[i][j] = 0;
        }
    }
}

int main(){

    int t; fin >> t;
    for(int i = 1; i <= t; ++i){
        int x, y, z, a, b, c;
        ll n;
        fin >> x >> y >> z >> a >> b >> c >> n;
        initializare();
        if(n > 2){


            mat2[1][1] = x;
            mat2[2][1] = y;
            mat2[3][1] = z;

            mat1[1][2] = 1;
            mat1[2][3] = 1;
            mat1[3][1] = c;
            mat1[3][2] = b;
            mat1[3][3] = a;

            ridicare(mat1, 3, 3, 3, 3, n - 2);
            inmultire(matf, 3, 3, mat2, 3, 1, finish);
            copiere(finish, matf, 3, 3);
            fout << matf[3][1] << '\n';
        }
        else if(n == 2) fout << z << '\n';
        else if(n) fout << y << '\n';
        else fout << x << '\n';
    }
    return 0;
}