#include <iostream>
#include <fstream>

using namespace std;

const int modul = 666013;
int matriceInitiala[3][1];

void Pow(int matriceBaza[3][3], int exp)
{
    int aux[3][3] = { {0, 0, 0}, {0, 0, 0}, {0, 0, 0} };

    while (exp > 0)
    {
        if (exp % 2 == 0)
        {
            for (int i = 0; i < 3; i++)
            {
                for (int o = 0; o < 3; o++)
                {
                    for (int j = 0; j < 3; j++)
                    {
                        aux[i][o] += matriceBaza[i][j] * matriceBaza[j][o] % modul;
                        aux[i][o] %= modul;
                    }
                }
            }
            for (int i = 0; i < 3; i++)
            {
                for (int o = 0; o < 3; o++)
                {
                    matriceBaza[i][o] = aux[i][o];
                    aux[i][o] = 0;
                }
            }

            exp /= 2;
        }
        else
        {
            for (int i = 0; i < 3; i++)
            {
                for (int o = 0; o < 3; o++)
                {
                    aux[i][0] += matriceBaza[i][o] * matriceInitiala[o][0] % modul;
                    aux[i][0] %= modul;
                }
            }
            for (int i = 0; i < 3; i++)
            {
                matriceInitiala[i][0] = aux[i][0];
                aux[i][0] = 0;
            }

            exp--;
        }
    }
}

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++)
    {
        cin >> matriceInitiala[0][0];
        cin >> matriceInitiala[1][0];
        cin >> matriceInitiala[2][0];

        int matriceBaza[3][3] = { {0, 1, 0}, {0, 0, 1}, {0, 0, 0} };
        cin >> matriceBaza[2][2];
        cin >> matriceBaza[2][1];
        cin >> matriceBaza[2][0];

        int nrZile;
        cin >> nrZile;
        Pow(matriceBaza, nrZile - 2);
        cout << matriceInitiala[2][0] << endl;
    }

    return 0;
}