#include <bits/stdc++.h>
#define mod 666013

using namespace std;

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

void inmultire(long long A[10][10],long long B[10][10])
{
    long long i,j,k,c[10][10];

    for(i=1;i<=3;i++)
    for(j=1;j<=3;j++)
    {
        c[i][j]=0;
        for(k=1;k<=3;k++)
            c[i][j]=(c[i][j]+(A[i][k]*B[k][j])%mod)%mod;
    }

    for(i=1;i<=3;i++)
    for(j=1;j<=3;j++)
        A[i][j]=c[i][j];
}

void ridicare_putere(long long A[10][10],long long putere)
{
    long long i,j,sol[10][10];

    for(i=1;i<=3;i++)
    for(j=1;j<=3;j++)
        if(i==j)sol[i][j]=1;
        else sol[i][j]=0;

    while(putere)
    {
        if(putere%2==0)
        {
            inmultire(A,A);
            putere/=2;
        }
        else
        {
            inmultire(sol,A);
            putere--;
        }
    }

    for(i=1;i<=3;i++)
    for(j=1;j<=3;j++)
        A[i][j]=sol[i][j];
}

long long x,y,z,a,b,c,n,i,j,T,A[10][10],B[10][10];
int main()
{
    f>>T;
    for(int pas=1;pas<=T;pas++)
    {
        f>>x>>y>>z>>a>>b>>c>>n;

        for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            A[i][j]=0;
        A[1][1]=x;A[1][2]=y;A[1][3]=z;

        for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            B[i][j]=0;

        for(i=1;i<3;i++)
        for(j=1;j<3;j++)
            if(i==j)
                B[i+1][j]=1;

        B[1][3]=c;B[2][3]=b;B[3][3]=a;
        ridicare_putere(B,n-3+1);

        inmultire(A,B);

        g<<A[1][3]%mod<<'\n';
    }
    return 0;
}