#include <bits/stdc++.h>

using namespace std;

struct Matrix{
    int value[4][4];

    Matrix(int a11, int a12, int a13, int a21, int a22, int a23, int a31, int a32, int a33)
    {
        value[1][1] = a11;
        value[1][2] = a12;
        value[1][3] = a13;
        value[2][1] = a21;
        value[2][2] = a22;
        value[2][3] = a23;
        value[3][1] = a31;
        value[3][2] = a32;
        value[3][3] = a33;
    }

    Matrix operator * (const Matrix M)
    {
        Matrix RES(0, 0, 0, 0, 0, 0, 0, 0, 0);

        for(int i = 1; i <= 3; ++i)
            for(int j = 1; j <= 3; ++j)
                for(int k = 1; k <= 3; ++k)
                    RES.value[i][j] = (RES.value[i][j] + 1LL*this->value[i][k]*M.value[k][j] % 666013) % 666013;

        return RES;
    }

    Matrix operator ^ (int N)
    {
        if(N == 0)
            return Matrix(1, 0, 0, 0, 1, 0, 0, 0, 1);

        if(N == 1)
            return *this;

        Matrix RES = *this^(N/2);

        RES = RES * RES;

        if(N & 1) RES = RES**this;

        return RES;
    }
};

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

    int T;
    fin >> T;

    for(int t = 1; t <= T; ++t)
    {
        int x, y, z, a, b, c, n;
        fin >> x >> y >> z >> a >> b >> c >> n;

        if(n == 2)
            fout << x + y + z;
        else{
            Matrix M(a, 1, 0, b, 0, 1, c, 0, 0);
            M = M ^ (n - 2);

            fout << (1LL*z*M.value[1][1]%666013 + 1LL*y*M.value[2][1]%666013 + 1LL*x*M.value[3][1]%666013) % 666013;
        }

        fout << '\n';
    }


}