#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define x first
#define y second
#define pi pair<int,int>
#define pl pair<ll,ll>

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const ll N=15005,INF=1e18,MOD=666013,M=1e2+5,inf=INT_MAX;

int t;
int ans[3][3],mult[3][3],aux[3][3];

void multip(int a[3][3],int b[3][3])
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            aux[i][j]=0;
        }
    }
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            {
                aux[i][j]+=a[i][k]*b[k][j];
                aux[i][j]%=MOD;
            }
        }
    }
}

void expmat(int b)
{
    while(b)
    {
        if(b&1)
        {
            multip(ans,mult);
            for(int i=0;i<3;i++)
            {
                for(int j=0;j<3;j++)
                {
                    ans[i][j]=aux[i][j];
                }
            }
        }
        multip(mult,mult);
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                mult[i][j]=aux[i][j];
            }
        }
        b/=2;
    }
}
void refresh()
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            ans[i][j]=mult[i][j]=0;
        }
    }
}

int main()
{
    fin>>t;
    for(int q=1;q<=t;q++)
    {
        int x,y,z,a,b,c,n;
        fin>>x>>y>>z>>a>>b>>c>>n;
        refresh();
        ans[0][0]=x;
        ans[0][1]=y;
        ans[0][2]=z;
        mult[1][0]=mult[2][1]=1;
        mult[0][2]=c;
        mult[1][2]=b;
        mult[2][2]=a;
        expmat(n-2);
        fout<<ans[0][2]<<'\n';
    }

}