#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

long long a[5][5],b[5][5],c[5][5],sol[5][5],t,n;

void inmultire(long long a[5][5],long long b[5][5])
{
    long long i,j,l,s;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
    {
        s=0;
        for(l=1;l<=3;l++)s+=a[i][l]*b[l][j],s%=MOD;
        c[i][j]=s;
    }
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)a[i][j]=c[i][j];
}

void pow_log(long long k)
{
    while(k>0)
    {
        if(k%2==1)inmultire(sol,b);
        inmultire(b,b);
        k/=2;
    }
}

int main()
{
    long long x,y,z,aa,bb,cc,i,j;
    f>>t;
    while(t--)
    {
        f>>x>>y>>z>>aa>>bb>>cc>>n;
        if(n==0)
        {
            g<<0;
            continue;
        }
        a[1][1]=x;
        a[1][2]=y;
        a[1][3]=z;
        b[2][1]=b[3][2]=1;
        b[1][3]=cc,b[2][3]=bb,b[3][3]=aa;
        sol[1][1]=sol[2][2]=sol[3][3]=1;
        pow_log(n-2);
        inmultire(a,sol);
        g<<a[1][3]<<'\n';

        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
            a[i][j]=b[i][j]=c[i][j]=sol[i][j]=0;
    }
    return 0;
}