#include <fstream>
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

#define mod 666013

int t,x,y,z,a,b,c,n;
long long sol[5][5],m1[5][5],m2[5][5];

void inm1()
{
    int i,j,k;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            m2[i][j]=0;

    for (k=1;k<=3;k++)
        for (i=1;i<=3;i++)
            for (j=1;j<=3;j++)
                m2[i][j]=(m2[i][j]+sol[i][k]*m1[k][j])%mod;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            sol[i][j]=m2[i][j];
}

void inm2()
{
    int i,j,k;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            m2[i][j]=0;
    for (k=1;k<=3;k++)
        for (i=1;i<=3;i++)
            for (j=1;j<=3;j++)
                m2[i][j]=(m2[i][j]+m1[i][k]*m1[k][j])%mod;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            m1[i][j]=m2[i][j];
}

void rid(int put)
{
    int i,j;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
        {
            m1[i][j]=0;
            sol[i][j]=0;
        }
    sol[1][1]=x;
    sol[1][2]=y;
    sol[1][3]=z;
    m1[2][1]=1;
    m1[3][2]=1;
    m1[1][3]=c;
    m1[2][3]=b;
    m1[3][3]=a;
    //afis();
    for (;put;put>>=1)
    {
        if (put&1)
        {
            inm1();
        }
        inm2();
        //afis();
    }

}

int main()
{
    int i,j;
    cin>>t;
    for (;t;t--)
    {
        cin>>x>>y>>z>>a>>b>>c>>n;
        if (n==3) cout<<z<<'\n';
        else
        {
            n-=2;
            rid(n);
            cout<<sol[1][3]<<'\n';
        }
    }
}