#include <bits/stdc++.h>
#define mod 666013


using namespace std;

ifstream f ("iepuri.in");
ofstream g ("iepuri.out");


int test;
int n;
int a[5][5];
int b[5][5];
int c[5][5];

int X,Y,Z,A,B,C;
void init(int x[5][5])
{
    for(int i=1; i<=3; ++i)
        for(int j=1; j<=3; ++j)
            x[i][j]=0;
}
void inmultire(int x[5][5], int y[5][5], int reciver[5][5])
{
    int z[5][5];
    init(z);
    for(int i=1; i<=3; ++i)
        for(int j=1; j<=3; ++j)
            for(int k=1; k<=3; ++k)
                z[i][j]+=(x[i][k]*y[k][j])%mod;


    for(int i=1; i<=3; ++i)
        for(int j=1; j<=3; ++j)
            reciver[i][j]=z[i][j]%mod;
}

void putere(int it)
{

    while(it>1)
    {
        if(it%2==1)
        {
            --it;
            inmultire(c, b, c);
        }
        else if(it%2==0)
        {
            it=it/2;
            inmultire(b, b, b);
        }
    }
}
int main()
{
    f>>test;

    for(int t=1; t<=test; ++t)
    {
        f>>X>>Y>>Z>>A>>B>>C>>n;

        init(b);
        init(a);
        init(c);
        a[1][1]=X;
        a[1][2]=Y;
        a[1][3]=Z;

        b[2][1]=b[3][2]=1;
        b[1][3]=C;
        b[2][3]=B;
        b[3][3]=A;

        c[1][1]=c[2][2]=c[3][3]=1;

        if(n==1)
            g<<(a[1][3])%mod<<"\n";
        else
        {
            putere(n-2);
            inmultire(b, c, b);

            inmultire(a, b, a);

            g<<(a[1][3])%mod<<"\n";
        }


    }
    return 0;
}