#include <fstream>

using namespace std;

const int MOD = 666013;

int A[3][3], B[3][3] = {{0, 0, 22}, {1, 0, 22}, {0, 1, 22}};

long long X, Y, Z;

int N;

ifstream f ("iepuri.in");

ofstream g ("iepuri.out");

void mul (int A[][3], int B[][3]) // A <-- A*B

{

    long long x[3][3];

    for (int i = 0; i < 3; i++)

        for (int j = 0; j < 3; j++)

        {

            x[i][j] = 0;

            for (int k = 0; k < 3; k++)

                x[i][j] += 1LL * A[i][k] * B[k][j];

        }

    for (int i = 0; i < 3; i++)

        for (int j = 0; j < 3; j++)

        {

            A[i][j] = x[i][j] % MOD;

        }
}

int putere (int n)

{

    int P[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

    while (n > 0)

    {

        while (n % 2 == 0)

        {

            mul (A, A);

            n /= 2;

        }

        mul (P, A);

        n--;

    }

    return (X * P[0][2] + Y * P[1][2] + Z * P[2][2]) % MOD;
}

int main()

{

    int T;

    f >> T;

    while (T--)

    {

        for (int i = 0; i < 3; i++)

            for (int j = 0; j < 2; j++)

                A[i][j] = B[i][j];

        f >> X >> Y >> Z >> A[2][2] >> A[1][2] >> A[0][2] >> N;

        g << putere (N - 2) << '\n';

    }

    f.close();

    g.close();

    return 0;
}