#include<fstream>
#include<iostream>
#include<cstring>
 
using namespace std;
 
ifstream f("iepuri.in");
ofstream g("iepuri.out");
 
long long Fin[4], Aux[4][4], Sol[4][4];
int t, x, y, z, a, b, c, n;
int const MOD = 666013;
 
void citire()
{
    f>>x>>y>>z>>a>>b>>c>>n;
}
 
void Mult(long long M[4][4], long long N[4][4])
{
    int i, j, k;
    for(i=1; i<4; i++)
        for(j=1; j<4; j++)
            Aux[i][j] = 0;
 
    for(i=1; i<4; i++)
        for(j=1; j<4; j++){
            for(k=1; k<4; k++)
                Aux[i][j] += M[i][k] * N[k][j];
            Aux[i][j] = Aux[i][j] % MOD;
        }
}
 
void Pow(int p)
{
    long long Mf[4][4];
    int i, j;
 
    for(i=1; i<4; i++)
        for(j=1; j<4; j++)
            Mf[i][j] = 0;
 
    Mf[2][1] = 1;
    Mf[3][2] = 1;
    Mf[1][3] = c;
    Mf[2][3] = b;
    Mf[3][3] = a;
 
    while(p){
        if(p%2 == 1){
            Mult(Sol, Mf);
            for(i=1; i<4; i++)
                for(j=1; j<4; j++)
                    Sol[i][j] = Aux[i][j];
        }
        Mult(Mf, Mf);
 
        for(i=1; i<4; i++)
            for(j=1; j<4; j++)
                Mf[i][j] = Aux[i][j];
        p = p/2;
    }
}
 
void MultArr(long long M[4], long long N[4][4])
{
    int i, j;
    for(i=1; i<4; i++){
        for(j=1; j<4; j++)
            Fin[i] += M[j] * N[j][i];
        Fin[i] = Fin[i] % MOD;
    }
}
 
int rez()
{
    long long Inc[4];
 
    for(int i=1; i<4; i++)
        for(int j=1; j<4; j++){
            Sol[i][j] = 0;
            if(i==j)
                Sol[i][j] = 1;
        }
 
    for(int i=1; i<4; i++)
        Fin[i] = 0;
 
    Pow(n-2);
 
    Inc[1] = x;
    Inc[2] = y;
    Inc[3] = z;
 
    MultArr(Inc, Sol);
 
    g<<Fin[3]<<"\n";
}
 
int main()
{
    f>>t;
    while(t--){
        citire();
        rez();
    }
    return 0;
}