#include <iostream>
#include <fstream>
#define b 666013
using namespace std;
ifstream fi("iepuri.in");
ofstream fo("iepuri.out");
long long a[10][10],m[10][10],r[10][10],p,n=3,zi[4],t,nrt,rsp[4];


void put(int p)
{
    if(p>1)
    {
        if(p%2==0)
        {
            put(p/2);
            ///a=a*a
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    r[i][j]=0;
                    for(int k=1;k<=n;k++)
                    {
                        r[i][j]=(r[i][j]%b + (a[i][k]%b * a[k][j]%b)%b)%b;
                    }
                }
            }

            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    a[i][j]=r[i][j];
                }
            }

        }
        else
        {
            put(p/2);
            ///a*a
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    r[i][j]=0;
                    for(int k=1;k<=n;k++)
                    {
                        r[i][j]=(r[i][j]%b + (a[i][k]%b * a[k][j]%b)%b)%b;
                    }
                }
            }

            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    a[i][j]=r[i][j];
                }
            }

            ///a*m
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    r[i][j]=0;
                    for(int k=1;k<=n;k++)
                    {
                        r[i][j]=(r[i][j]%b + (a[i][k]%b * m[k][j]%b)%b)%b;
                    }
                }
            }

            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    a[i][j]=r[i][j];
                }
            }
        }
    }
}


int main()
{
    fi>>t;
    for(nrt=1;nrt<=t;nrt++)
    {
        a[1][1]=a[1][2]=a[2][2]=a[3][1]=0;
        a[2][1]=a[3][2]=1;
        fi>>zi[1]>>zi[2]>>zi[3];
        fi>>a[3][3]>>a[2][3]>>a[1][3];
        fi>>p;
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
            {
                m[i][j]=a[i][j];
            }
        }
        put(p-2);

        for(int i=1;i<=n;i++)
        {
            rsp[i]=0;
            for(int j=1;j<=n;j++)
            {
                rsp[i]=(rsp[i]%b + (zi[j]%b * a[j][i]%b)%b)%b;
            }
        }
        fo<<rsp[3]<<endl;
    }
}