#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;
}