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

long long mul[3][3], a[3][3], b[3][3], a1, b1, c1;
void inm(long long a[3][3], long long b[3][3])
{
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            mul[i][j] = 0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                mul[i][j] = (mul[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
}
void logput(int p)
{
    if (p == 1)
        a[0][0] = 0, a[0][1] = 0, a[0][2] = c1, a[1][0] = 1, a[1][1] = 0, a[1][2] = b1, a[2][0] = 0, a[2][1] = 1, a[2][2] = a1;
    else
    {
        logput(p / 2);
        inm(a, a);
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                a[i][j] = mul[i][j];
        if (p % 2 == 1)
        {
            inm(a, b);
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                    a[i][j] = mul[i][j];
        }
    }
}

int main()
{
    ifstream cin("iepuri.in");
    ofstream cout("iepuri.out");
    int t, x, y, z, n, i;
    cin >> t;
    for (i = 1; i <= t; i++)
    {
        cin >> x >> y >> z >> a1 >> b1 >> c1 >> n;
        b[0][0] = 0, b[0][1] = 0, b[0][2] = c1, b[1][0] = 1, b[1][1] = 0, b[1][2] = b1, b[2][0] = 0, b[2][1] = 1, b[2][2] = a1;
        logput(n);
        b[0][0] = x, b[0][1] = y, b[0][2] = z, b[1][0] = 0, b[1][1] = 0, b[1][2] = 0, b[2][0] = 0, b[2][1] = 0, b[2][2] = 0;
        inm(b, a);
        cout << mul[0][0] << '\n';
    }
}