#include <bits/stdc++.h>

#define MOD 666013

using namespace std;

class Matrix {
private:
    vector<vector<int>> M;
public:
    Matrix(int n, int m) {
        M.resize(n, vector<int>(m, 0));
    }

    int get(int i, int j) {
        return M[i][j];
    }

    void set(int i, int j, int val) {
        M[i][j] = val;
    }

    int lines() {
        return M.size();
    }

    int columns() {
        return M[0].size();
    }

    friend Matrix operator + (Matrix A, const Matrix& B) {
        assert(A.M.size() == B.M.size() && A.M[0].size() == B.M[0].size());
        for(size_t i = 0; i < A.M.size(); i++) {
            for(size_t j = 0; j < A.M[0].size(); j++) {
                A.M[i][j] = (A.M[i][j] + B.M[i][j]) % MOD;
            }
        }
        return A;
    }
    friend Matrix operator * (Matrix A, const Matrix& B) {
        assert(A.M[0].size() == B.M.size());
        Matrix C(A.M.size(), B.M[0].size());
        for(size_t i = 0; i < A.M.size(); i++) {
            for(size_t j = 0; j < B.M[0].size(); j++) {
                for(size_t k = 0; k < A.M[0].size(); k++) {
                    C.M[i][j] = (C.M[i][j] + 1LL * A.M[i][k] * B.M[k][j]) % MOD;
                }
            }
        }
        return C;
    }
};

Matrix logPow(Matrix base, int exp) {
    assert(base.lines() == base.columns());

    Matrix ans(base.lines(), base.columns());
    ans.set(0, 0, 1);
    ans.set(1, 1, 1);
    for(int i = 0; i <= 30; i++) {
        if(exp & (1 << i)) {
            ans = ans * base;
        }
        base = base * base;
    }

    return ans;
}

void printMat(Matrix mat) {
    for(int i = 0; i < mat.lines(); i++) {
        for(int j = 0; j < mat.columns(); j++) {
            printf("%d ", mat.get(i, j));
        }
        printf("\n");
    }
}

void test_case() {
    int x,y,z,a,b,c,n;
    scanf("%d %d %d",&x,&y,&z);
    scanf("%d %d %d",&a,&b,&c);
    scanf("%d",&n);
    Matrix base(3,3);
    base.set(0,1,1);
    base.set(1,2,1);
    base.set(2,0,c);
    base.set(2,1,b);
    base.set(2,2,a);
    Matrix start(3,1);
    start.set(0,0,x);
    start.set(1,0,y);
    start.set(2,0,z);
    printf("%d\n",(logPow(base, n) * start).get(0,0) );


}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--) {
        test_case();
    }

    return 0;
}