#include <cstdio>
#include <cstring>
using namespace std;
typedef long long i64;
const i64 MOD = 666013;
i64 M[3][3] = {{0, 0, 0},
{1, 0, 0},
{0, 1, 0}};
i64 I[3][3] = {{1, 0, 0},
{0, 1, 0},
{0, 0, 1}};
void multiply(i64 A[][3], i64 B[][3], i64 C[][3]) {
int i, j, k;
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
A[i][j] = 0;
for (k = 0; k < 3; ++k)
A[i][j] += B[i][k] * C[k][j];
A[i][j] = A[i][j] % MOD;
}
}
}
void mcopy(i64 A[][3], i64 B[][3]) {
//memcpy(A, B, sizeof(B));
int i, j;
for (i = 0; i < 3; ++i)
for (j = 0; j < 3; ++j)
A[i][j] = B[i][j];
}
int main() {
int x, y, z, n, k0, k1, i, O;
i64 S[2][3][3], V[2][3][3];
freopen("iepuri.in", "r", stdin);
freopen("iepuri.out", "w", stdout);
scanf("%d", &O);
while (O--) {
mcopy(V[0], M); mcopy(S[0], I);
scanf("%d%d%d %lld%lld%lld %d", &x, &y, &z
, &V[0][0][0]
, &V[0][0][1]
, &V[0][0][2]
, &n);
k0 = k1 = 0;
for (n -= 2; n > 0; n >>= 1) {
if (n % 2) {
multiply(S[1-k0], S[k0], V[k1]);
k0 = 1-k0;
}
multiply(V[1-k1], V[k1], V[k1]);
k1 = 1-k1;
}
printf("%lld\n", (1LL*z*S[k0][0][0] + 1LL*y*S[k0][0][1] + 1LL*x*S[k0][0][2])%MOD);
}
return 0;
}