#include <bits/stdc++.h>
#define MOD 666013
#define int long long

using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
int t, tudor;
struct mat{
    int n, m;
    int mt[5][5];
};
mat litan, rizz, rez;
mat mult(mat p, mat q){
    mat aux;
    aux.n = p.n;
    aux.m = p.m;
    for(int i = 1; i <= p.n; i++){
        for(int j = 1; j <= p.m; j++){
            aux.mt[i][j] = 0;
            for(int k = 1; k <= p.m; k++){
                aux.mt[i][j] += (p.mt[i][k] * q.mt[k][j]) % MOD;
                aux.mt[i][j] %= MOD;
            }
        }
    }
    return aux;
}
mat EuIlIubescPe(mat p, int q){
    mat aux;
    aux.n = p.n;
    aux.m = p.m;
    if(q == 1){
        aux = p;
    }
    else if(q % 2 == 0){
        mat aux1 = EuIlIubescPe(p, q / 2);
        aux = mult(aux1, aux1);
    }
    else{
        mat aux1 = EuIlIubescPe(p, q / 2);
        aux = mult(mult(aux1, aux1), p);
    }
    return aux;
}

signed main()
{
    fin >> t;
    rez.n = 1;
    rez.m = 3;
    litan.n = 3;
    litan.m = 3;
    litan.mt[2][1] = 1;
    litan.mt[3][2] = 1;
    while(t--){
        fin >> rez.mt[1][1] >> rez.mt[1][2] >> rez.mt[1][3]
        >> litan.mt[3][3] >> litan.mt[2][3] >> litan.mt[1][3] >> tudor;
        tudor -= 2;
        rizz = EuIlIubescPe(litan, tudor);
        rez = mult(rez, rizz);
        fout << rez.mt[1][3] << "\n";
    }
    return 0;
}