#include <fstream>

using namespace std;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

int rez[5][5], m[5][5],aux[5][5], f[5][2], r[5][2];

void umplere(int a[5][5])
{
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            a[i][j]=0;
        }
    }
}

void umplere2()
{
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            rez[i][j]=0;
        }
    }
    for(int i=1;i<=4;i++)
        rez[i][i]=1;
}

void umplere3()
{
    for(int i=1;i<=4;i++)
    {
        r[i][1]=0;
    }
}

void inmultire(int a[5][5], int b[5][5])
{
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            for(int k=1;k<=4;k++)
            {
                aux[i][j]+=(a[i][k]*b[k][j])%666013;
            }
        }
    }
    // ii dam lui a valoarea lui aux
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            a[i][j]=aux[i][j];
        }
    }
    umplere(aux);
}

void afisare(int a[5][5], int b[5][2])
{
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=1;j++)
        {
            for(int k=1;k<=4;k++)
            {
                r[i][j]+=(a[i][k]*b[k][j])%666013;
            }
        }
    }
    cout<<r[4][1]<<'\n';
}

int main()
{
    int n,t;
    cin>>t;
    for(int i1=1;i1<=t;i1++)
    {
        umplere(m);
        for(int i=1;i<=3;i++)
        {
            cin>>f[i+1][1];
        }
        for(int i=4;i>1;i--)
        {
            cin>>m[4][i];
        }
        m[1][2]=1;
        m[2][3]=1;
        m[3][4]=1;
        cin>>n;
        if(n==1)
            cout<<f[3][1];
        else if(n==2)
            cout<<f[4][1];
        else
        {
            umplere2();
            umplere(aux);
            umplere3();
            n=n-2;
            while(n!=0)
            {
                if(n%2==1)
                {
                    inmultire(rez,m);
                    n--;
                }
                else
                {
                    inmultire(m,m);
                    n/=2;
                }
            }
            afisare(rez,f);
        }
    }
    return 0;
}