#include <iostream>
#include <fstream>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
const int MOD = 666013;
void inmultire(int a[3][3], int b[3][3])
{
    int c[3][3];
    int i, j, k;
    for (i = 0; i <= 2; i++)for (j = 0; j <= 2; j++)
    {
        c[i][j] = 0;
        for (k = 0; k <= 2; k++) 
            c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
    }
    for (i = 0; i <= 2; i++) 
        for (j = 0; j <= 2; j++) 
            a[i][j] = c[i][j];
}
void putere(int sol[3][3], int mx[3][3], int k)
{
    while (k)
    {
        if (k % 2 == 1) 
        { 
            inmultire(sol, mx); 
            k--; 
        }
        else 
        { 
            inmultire(mx, mx); 
            k = k / 2; 
        }
    }
}
int ox[3][3], mx[3][3], sol[3][3];
int main()
{
    int ct, teste;
    f >> teste;

    int x, y, z, a, b, c, n, i, j;
    for (ct = 1; ct <= teste; ct++)
    {
        f >> x >> y >> z >> a >> b >> c >> n;
        for (i = 0; i <= 2; i++) 
            for (j = 0; j <= 2; j++) 
                ox[i][j] = 0;
        ox[0][0] = x; 
        ox[0][1] = y; 
        ox[0][2] = z;
        for (i = 0; i <= 2; i++) 
            for (j = 0; j <= 2; j++) 
                mx[i][j] = 0;
        mx[0][2] = c; 
        mx[1][2] = b; 
        mx[2][2] = a;
        mx[1][0] = 1; 
        mx[2][1] = 1;
        for (i = 0; i <= 2; i++) 
            for (j = 0; j <= 2; j++) 
                sol[i][j] = 0;
        sol[0][0] = 1; 
        sol[1][1] = 1; 
        sol[2][2] = 1;
        putere(sol, mx, n);
        inmultire(ox, sol);
        g << ox[0][0] << "\n";
    }
    return 0;
}