#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

void inmultire(long a[4][4],long b[4][4])
{int i,j;
long c[4][4];
 c[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1]+a[1][3]*b[3][1])%mod;
 c[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2]+a[1][3]*b[3][2])%mod;
 c[1][3]=(a[1][1]*b[1][3]+a[1][2]*b[2][3]+a[1][3]*b[3][3])%mod;
 c[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1]+a[2][3]*b[3][1])%mod;
 c[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2]+a[2][3]*b[3][2])%mod;
 c[2][3]=(a[2][1]*b[1][3]+a[2][2]*b[2][3]+a[2][3]*b[3][3])%mod;
 c[3][1]=(a[3][1]*b[1][1]+a[3][2]*b[2][1]+a[3][3]*b[3][1])%mod;
 c[3][2]=(a[3][1]*b[1][2]+a[3][2]*b[2][2]+a[3][3]*b[3][2])%mod;
 c[3][3]=(a[3][1]*b[1][3]+a[3][2]*b[2][3]+a[3][3]*b[3][3])%mod;

for(i=1;i<=3;i++)
    for(j=1;j<=3;j++)
    a[i][j]=c[i][j];
}



int main()
{int i,j;
long rezultat,v,b,c,n,x,y,z,t;
long a[4][4],r[4][4];
fin>>t;
while(t--){
    fin>>x>>y>>z>>v>>b>>c>>n;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        {r[i][j]=0;if(i==j)r[i][j]=1;}
    for(i=1;i<=3;i++)a[1][i]=0;a[1][2]=1;
    for(i=1;i<=3;i++)a[2][i]=0;a[2][3]=1;
    a[3][1]=c;a[3][2]=b;a[3][3]=v;

    for(i=0;(1<<i)<=n;i++)
    {
        if(n & (1<<i))
            inmultire(r,a);
        inmultire(a,a);
    }


    rezultat=(r[1][1]*x+r[1][2]*y+r[1][3]*z)%mod;
    fout<<rezultat<<'\n';
    }

}