#include <bits/stdc++.h>
#define M 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");

int t,n,x,y,z,a,b,c,Z[4][4],sol[4][4];

void RidicareLog(int p)
{   if(p==1)
    {   for(int i=1; i<=3; i++)
            for(int j=1; j<=3; j++)
                sol[i][j]=Z[i][j];
        return;
    }
    RidicareLog(p/2);
    int aux[4][4];
    for(int i=1; i<=3; i++)
        for(int sum,j=1; j<=3; j++)
        {   sum=0;
            for(int k=1; k<=3; k++)
                sum=(sum%M+sol[i][k]%M*sol[k][j]%M)%M;
            aux[i][j]=sum%M;

        }
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            sol[i][j]=aux[i][j];
    if(p%2)
        for(int i=1; i<=3; i++)
            for(int sum,j=1; j<=3; j++)
            {   sum=0;
                for(int k=1; k<=3; k++)
                    sum=(sum%M+sol[i][k]%M*Z[k][j]%M)%M;
                aux[i][j]=sum%M;
            }
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            sol[i][j]=aux[i][j];
}

int main()
{   Z[2][1]=Z[3][2]=1;
    f>>t;
    while(t--)
    {   f>>x>>y>>z>>a>>b>>c>>n;
        Z[1][3]=c;
        Z[2][3]=b;
        Z[3][3]=a;
        RidicareLog(n-2);
        int rez=(x*sol[1][3]%M+y*sol[2][3]%M+z*sol[3][3]%M)%M;
        g<<rez<<'\n';
    }
    f.close(); g.close(); return 0;
}