#include <bits/stdc++.h>
#define mod 666013
using namespace std;

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

/**
                                0 0 C
(an an+1 an+2) = (an-1 an an+1) 1 0 B
                                0 1 A
                               n - 3
                            0 0 C
(an-2 an-1 an) = (a1 a2 a3) 1 0 B
                            0 1 A

*/

int a[3][3], c[3][3];

void Inmultire(int a[3][3], int b[3][3])
{
    int i, j, k;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            c[i][j] = 0;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            for (k = 0; k < 3; k++)
                c[i][j] = (1ll * c[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
}

void Copiaza(int a[3][3], int b[3][3])
{
    int i, j;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            a[i][j] = b[i][j];
}

void Exp(int n, int rez[3][3])
{
    int i, j;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            if (i == j) rez[i][j] = 1;
            else rez[i][j] = 0;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            Inmultire(rez, a);
            Copiaza(rez, c);
        }
        n /= 2;
        Inmultire(a, a);
        Copiaza(a, c);
    }
}

int main()
{
    int t, rez[3][3], n, X, Y, Z, A, B, C;
    fin >> t;
    a[1][0] = a[1][2] = 1;
    while (t--)
    {
        fin >> X >> Y >> Z >> A >> B >> C >> n;
        a[2][2] = A; a[1][2] = B; a[0][2] = C;
        a[1][0] = a[2][1] = 1;
        a[0][0] = a[0][2] = a[1][0] = a[1][1] = 0;

        Exp(n - 2, rez);

        fout << (1ll * X * rez[0][2] +
                1ll * Y * rez[1][2] +
                1ll * Z * rez[2][2]) % mod << "\n";
    }
    return 0;
}