#include <iostream>
#include <fstream>

using namespace std;

const int mod = 666013;

void InmultireMatrici(int a[3][3], int b[3][3], int (&rez)[3][3])
{
    for(int i = 0; i < 3; i++)
    {
        for(int o = 0; o < 3; o++)
        {
            rez[i][o] = 0;
            for(int j = 0; j < 3; j++)
            {
                rez[i][o] += ((long long)a[i][j] * (long long)b[j][o]) % mod;
                rez[i][o] %= mod;
            }
        }
    }
}

void RidicarePatratMatrice(int baza[3][3], int exp, int (&rez)[3][3])
{
    for(int i = 0; i < 3; i++)
    {
        for(int o = 0; o < 3; o++)
            rez[i][o] = 0;
    }
    rez[0][0] = 1;
    rez[1][1] = 1;
    rez[2][2] = 1;

    while(exp > 0)
    {
        if(exp % 2 == 0)
        {
            int tmp[3][3];
            InmultireMatrici(baza, baza, tmp);
            for(int i = 0; i < 3; i++)
            {
                for(int o = 0; o < 3; o++)
                    baza[i][o] = tmp[i][o];
            }
            exp /= 2;
        }
        else
        {
            int tmp[3][3];
            InmultireMatrici(baza, rez, tmp);
            for(int i = 0; i < 3; i++)
            {
                for(int o = 0; o < 3; o++)
                    rez[i][o] = tmp[i][o];
            }
            exp--;
        }
    }
}

void RezolvareSet()
{
    int fibonacci[3];
    cin >> fibonacci[0];
    cin >> fibonacci[1];
    cin >> fibonacci[2];

    int matriceBaza[3][3];
    for(int i = 0; i < 3; i++)
    {
        for(int o = 0; o < 3; o++)
            matriceBaza[i][o] = 0;
    }
    matriceBaza[0][1] = 1;
    matriceBaza[1][2] = 1;
    cin >> matriceBaza[2][2];
    cin >> matriceBaza[2][1];
    cin >> matriceBaza[2][0];

    int ziTinta;
    cin >> ziTinta;

    int bazaInmultita[3][3];
    RidicarePatratMatrice(matriceBaza, ziTinta - 2, bazaInmultita);

    int rez[3];
    for(int i = 0; i < 3; i++)
    {
        rez[i] = 0;
        for(int o = 0; o < 3; o++)
        {
            rez[i] += ((long long)bazaInmultita[i][o] * (long long)fibonacci[o]) % mod;
            rez[i] %= mod;
        }
    }

    cout << rez[2] << endl;
}

int main()
{
    ifstream in("iepuri.in");
    cin.rdbuf(in.rdbuf());
    ofstream out("iepuri.out");
    cout.rdbuf(out.rdbuf());

    int nrSeturi;
    cin >> nrSeturi;
    for(int i = 0; i < nrSeturi; i++)
    {
        RezolvareSet();
    }

    return 0;
}