#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int MAT_DIM = 4;
const int MOD = 666013;

class Matrix {
public:
    int h, w;
    int M[MAT_DIM][MAT_DIM];

    Matrix(int H, int W, int c = 0) {
        memset(M, 0, sizeof(M[0][0]) * MAT_DIM * MAT_DIM);
        h = H;
        w = W;
        for(int i = 1; i <= h; i++) M[i][i] = c;
    }
    Matrix operator *(const Matrix &other) const {
        int i, j, t;
        Matrix ret(this->h, other.w);

        for(i = 1; i <= ret.h; i++) {
            for(j = 1; j <= ret.w; j++) {
                for(t = 1; t <= this->w; t++) {
                    ret.M[i][j] += 1LL * this->M[i][t] * other.M[t][j] % MOD;
                    ret.M[i][j] %= MOD;
                }
            }
        }

        return ret;
    }
    Matrix operator ^(int exp) const {
        Matrix pow = *this, ret(this->h, this->w, 1);
        while(exp) {
            if(exp & 1) ret = ret * pow;
            pow = pow * pow;
            exp >>= 1;
        }
        return ret;
    }
};

int main() {
    int x, y, z, a, b, c, n, t, i;
    Matrix valmat(1, 3), recmat(3, 3);

    in >> t;
    while(t--) {
        in >> x >> y >> z >> a >> b >> c >> n;

        valmat.M[1][1] = x;
        valmat.M[1][2] = y;
        valmat.M[1][3] = z;

        if(n <= 3) {
            out << valmat.M[1][n] << '\n';
        }
        else {
            recmat.M[1][3] = c;
            recmat.M[2][1] = 1;
            recmat.M[2][3] = b;
            recmat.M[3][2] = 1;
            recmat.M[3][3] = a;

            valmat = valmat * (recmat ^ (n - 2));
            out << valmat.M[1][3] << '\n';
        }
    }

    return 0;
}