#include <fstream>
using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
int n,a[4][4],b[4][4],c[4][4],i[4][4],t,A,B,C,x,y,z,j;
const int mod=666013;

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

void copiere(int a[4][4],int b[4][4])
{
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            a[i][j]=b[i][j];
}

void plog (int n,int a[4][4])
{
    if (n==1)
        return;
    plog(n/2,a);
    produs(a,a,b);
    if (n%2!=0)
        produs(b,i,a);
    else
        copiere (a,b);
}

int main()
{
    fin>>t;
    for (j=1;j<=t;j++)
    {
        fin>>x>>y>>z>>A>>B>>C>>n;
        i[1][1]=a[1][1]=C;
        i[2][1]=a[2][1]=B;
        i[3][1]=a[3][1]=A;
        i[1][2]=a[1][2]=i[2][3]=a[2][3]=1;
        plog(n-2,a);
        fout<<(a[1][1]*z*1ll+a[2][1]*y*1ll+a[3][1]*x*1ll)%mod;
        fout<<'\n';
    }
    return 0;
}