#include <bits/stdc++.h>
#define modulo 666013

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

int t, n, a, b, c, p[7][7], prod[7][7], v[7][7], f2[7][7];

void Curat(int mat[7][7])
{
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
            mat[i][j] = 0;
}

void Inmultire(int x[7][7], int y[7][7])
{
    Curat(p);

    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++){
            long long s = 0;
            for(int k = 1; k <= 3; k++)
                s += (1LL * x[i][k] * y[k][j]);
            p[i][j] = s % modulo;
        }
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
            x[i][j] = p[i][j];
}
void Ridicare()
{
    Curat(prod);
    prod[1][1] = prod[2][2] = prod[3][3] = 1;

    while(n)
    {
        if(n % 2)
            Inmultire(prod, v);
        n /= 2;
        Inmultire(v, v);
    }

    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
            v[i][j] = prod[i][j];
}
void Curatare()
{
    Curat(v);
    v[2][1] = 1;
    v[3][2] = 1;
    v[1][3] = c;
    v[2][3] = b;
    v[3][3] = a;
}

void Citire()
{

    fin >> t;
    for(int i = 1; i <= t; i++)
    {
        fin >> f2[1][1] >> f2[1][2] >> f2[1][3] >> a >> b >> c >> n;
        n -= 2;
        Curatare();
        Ridicare();
        Inmultire(f2, v);
        fout << f2[1][3] << "\n";
    }

}
int main()
{
    Citire();
    return 0;
}