#include <bits/stdc++.h>

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const int MOD = 666013;

int fib[4][2], rezm[4][4];
int baza[4][4]= {{0, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};

void er(long long exp)
{
    int aux[4][4], rez;
    int i, j, k;
    while(exp)
    {
        if(exp%2==0)
        {
            exp/=2;
            for(i=1; i<=3; i++)
            {
                for(j=1; j<=3; j++)
                {
                    rez=0;
                    for(k=1; k<=3; k++)
                    {
                        rez+=baza[i][k]*baza[k][j]%MOD;
                    }
                    aux[i][j]=rez;
                }
            }
            for(i=1; i<=3; i++)
            {
                for(j=1; j<=3; j++)
                {
                    baza[i][j]=aux[i][j];
                }
            }
        }
        else
        {
            exp--;
            for(i=1; i<=3; i++)
            {
                for(j=1; j<=3; j++)
                {
                    rez=0;
                    for(k=1; k<=3; k++)
                    {
                        rez+=rezm[i][k]*baza[k][j]%MOD;
                    }
                    aux[i][j]=rez;
                }
            }
            for(i=1; i<=3; i++)
            {
                for(j=1; j<=3; j++)
                {
                    rezm[i][j]=aux[i][j];
                }
            }
        }
    }
}

int main()
{
    long long i, j, k, w, rez;
    long long t, x, y, z, n;
    fin >> t;
    for(w=1; w<=t; w++)
    {
        for(i=1; i<=3; i++)
        {
            for(j=1; j<=3; j++)
            {
                baza[i][j]=0;
                rezm[i][j]=0;
            }
        }
        fin >> fib[1][1] >> fib[2][1] >> fib[3][1] >> baza[3][3] >> baza[3][2] >> baza[3][1] >> n;
        baza[1][2]=baza[2][3]=1;
        rezm[1][1]=rezm[2][2]=rezm[3][3]=1;
        er(n);
        rez=0;
        for(k=1; k<=3; k++)
        {
            rez+=rezm[1][k]*fib[k][1]%MOD;
        }
        fout << rez << "\n";
    }
    return 0;
}