#include <fstream>

using namespace std;

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

int n;
const int mod = 666013;

int y[4][4];
int x[4];
int z[4][4];

void inmultire(int m1[4][4], int m2[4][4])
{
    int aux[4][4] = { 0 };
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
        {
            for (int k = 1; k <= 3; k++)
                aux[i][j] += (m1[i][k] * m2[k][j]) % mod;
        }
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            z[i][j] = aux[i][j]%mod;
}

void putere(int p)
{
    if (p == 1)
    {
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                z[i][j] = y[i][j];
    }
    else
    {
        if (p % 2 == 0)
        {
            putere(p / 2);
            inmultire(z, z);

        }
        else
        {
            putere(p - 1);
            inmultire(z, y);

        }
    }
}

int main()
{
    int t;
    fin >> t;
    y[2][1] = 1;
    y[3][2] = 1;
    for (int i = 1; i <= t; i++)
    {
        int a, b, c, n;
        fin >> x[1] >> x[2] >> x[3] >> a >> b >> c >> n;

        y[1][3] = c;
        y[2][3] = b;
        y[3][3] = a;
        putere(n - 2);
        fout << (x[1] * z[1][3] + x[2] * z[2][3] + x[3] * z[3][3]) % mod << endl;

    }
    return 0;
}