#include <fstream>
#define N 3
#define M 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

struct matrix{
    int m[N][N];
    matrix(){
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                m[i][j] = 0;
    }
    matrix operator*(const matrix& b){
        matrix c;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                for(int k = 0; k < N; ++k)
                    c.m[i][j] = (c.m[i][j] + 1LL * m[i][k] * b.m[k][j]) % M;
        return c;
    }
};

matrix unit;
matrix putere(matrix x, int p){
    matrix s = unit;
    for(int i = 0; (1 << i) <= p; ++i){
        if(p & (1 << i))
            s = s * x;
        x = x * x;
    }
    return s;
}


matrix M1, M2, NUZ;
int t, x, y, z, a, b, c, n;
int main()
{
    unit.m[0][0] = 1;
    unit.m[1][1] = 1;
    unit.m[2][2] = 1;
    M2.m[1][0] = 1;
    M2.m[2][1] = 1;

    fin>>t;
    for(int i = 1; i <= t; ++i){
        fin >> x >> y >> z >> a >> b >> c >> n;
        if(n == 3)
            fout<<z<<'\n';
        else {
            M1.m[0][0] = x;
            M1.m[0][1] = y;
            M1.m[0][2] = z;

            M2.m[0][2] = c;
            M2.m[1][2] = b;
            M2.m[2][2] = a;

            matrix aux = putere(M2, n - 2);
            matrix rez = M1 * aux;
            fout<<rez.m[0][2]<<'\n';
        }
    }
    return 0;
}