#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
int sol[4][4];
void inm(int a[][4],int b[][4])
{
    int c[4][4],i,j,k;
    memset(c,0,sizeof(c));
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            for(k=0;k<3;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%mod;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            a[i][j]=c[i][j];
}

void put(int  a[][4],int p)
{
    memset(sol,0,sizeof(sol));
    sol[0][0]=sol[1][1]=sol[2][2]=1;
    for(int i=0;(1LL<<i)<=p;i++)
    {
        if((1<<i)&p)
        {
            inm(sol,a);
        }
        inm(a,a);
    }
}

int main()
{long long t,a,b,c,x,y,z,n;
int m[4][4];
in>>t;
while(t--)
{
    in>>x>>y>>z>>a>>b>>c>>n;
    memset(m,0,sizeof(m));
    m[0][0]=a;
    m[0][1]=b;
    m[0][2]=c;
    m[1][0]=m[2][1]=1;
    put(m,n-2);
    out<<((z*sol[0][0])%mod+(y*sol[0][1])%mod+(x*sol[0][2])%mod)%mod<<'\n';
}
    return 0;
}