#include <bits/stdc++.h>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
struct matrix
{
    int n, m, mat[5][5];
    matrix(int n, int m, int x, int y, int z)
    {
        memset(this -> mat, 0, sizeof this -> mat);
        this -> n = n;
        this -> m = m;
        if (n == 1)
        {
            this -> mat[1][1] = x;
            this -> mat[1][2] = y;
            this -> mat[1][3] = z;
        }
        else
        {
            this -> mat[2][1] = 1;
            this -> mat[3][2] = 1;
            this -> mat[1][3] = z;
            this -> mat[2][3] = y;
            this -> mat[3][3] = x;
        }
    }
    matrix(int n, int m)
    {
        this -> n = n;
        this -> m = m;
        memset(this -> mat, 0, sizeof this -> mat);
        this -> mat[1][1] = 1;
        this -> mat[2][2] = 1;
        this -> mat[3][3] = 1;
    }
    matrix(int n, int m, int _)
    {
        this -> n = n;
        this -> m = m;
        memset(this -> mat, 0, sizeof this -> mat);
    }
    matrix operator*(const matrix other)
    {
        matrix aux(this -> n, other.m, 0);
        for (int i = 1; i <= this -> n; i++)
            for(int j = 1; j <= other.m; j++)
                for(int y = 1; y <= other.n; y++)
                    aux.mat[i][j] += (1ll * this -> mat[i][y] * other.mat[y][j]) % 666013,
                                     aux.mat[i][j] %= 666013;
        return aux;
    }
};
void solve()
{
    int x, y, z, a, b, c, n;
    f >> x >> y >> z >> a >> b >> c >> n;
    matrix init(1, 3, x, y, z), mat(3, 3, a, b, c), unit(3, 3);
    n -= 2;
    while(n)
    {
        if(n&1)
            unit = unit * mat;
        mat = mat * mat;
        n >>= 1;
    }
    init = init * unit;
    g << init.mat[1][3] << '\n';
}
int main()
{
    int q;
    f >> q;
    while (q--)
        solve();
    return 0;
}