#include <bits/stdc++.h>
#define dim 1000002
#define int long long
#define mod 666013// 1000000007
using namespace std;
ifstream fin ("iepuri.in");
ofstream fout("iepuri.out");
int iep[4][4],m[4][4],sol[4][4];

void inm (int a[4][4],int b[4][4])
{
    int i,j,k,c[4][4];
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
        {
            int nr=0;
            for (k=1;k<=3;k++)
                nr=(nr+a[i][k]*b[k][j])%mod;
            c[i][j]=nr;
        }
     for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            a[i][j]=c[i][j];
}


void lgput (long long exp)
{
    while (exp!=0)
    {
        if (exp%2==1)
            inm(sol,m);
        exp/=2;
        inm(m,m);
    }
}

int32_t  main()
{
    int t,n;
    fin>>t;
    while (t--)
    {
         m[1][1]=0,m[1][2]=0,m[2][1]=1;
        m[2][2]=0,m[3][1]=0,m[3][2]=1;
        fin>>iep[1][1]>>iep[1][2]>>iep[1][3];
        fin>>m[3][3]>>m[2][3]>>m[1][3]>>n;
        if (n==0)
            fout<<0<<'\n';
        else{
        sol[1][1]=0,sol[1][2]=0,sol[2][1]=1;
        sol[2][2]=0,sol[3][1]=0,sol[3][2]=1;
        sol[3][3]=m[3][3];
        sol[2][3]=m[2][3];
        sol[1][3]=m[1][3];
        lgput(n-3);
        inm(iep,sol);
        fout<<iep[1][3]<<'\n';
        }
    }
    return 0;
}