#include <bits/stdc++.h>
using namespace std;
ifstream r("iepuri.in");
ofstream w("iepuri.out");
const int mod=666013;
long long m[4][4], mat[4][4];
void inmultire(long long mat1[][4],long long mat2[][4])
{
    int aux[4][4]= {};
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            for(int k=1; k<=3; k++)
            {
                aux[i][j]+=(mat1[i][k]*mat2[k][j])%mod;
            }
        }
    }
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            mat[i][j]=aux[i][j]%mod;
        }
    }
}
void putere(long long p)
{
    if(p==1)
    {
        for(int i=1; i<=3; i++)
        {
            for(int j=1; j<=3; j++)
            {
                mat[i][j]=m[i][j];
            }
        }
        return ;
    }
    if(p%2==0)
    {
        putere(p/2);
        inmultire(mat,mat);
    }
    else
    {
        putere(p-1);
        inmultire(m,mat);
    }
}
int main()
{
    int t;
    r>>t;
    m[1][2]=1;
    m[2][3]=1;
    while(t--)
    {
        int x, y, z, a, b, c, n;
        r>>x>>y>>z>>a>>b>>c>>n;
        m[1][1]=a;
        m[2][1]=b;
        m[3][1]=c;
        putere(n-2);
        w<<(z*mat[1][1]+y*mat[2][1]+x*mat[3][1])%mod<<"\n";
    }
    return 0;
}