#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("iepuri.in");
ofstream out ("iepuri.out");
int a[5][5],rez[5][5],ini[5][5],mrez[5][5],x,y,z,A,B,C;
void initializare_a(int a[5][5])
{
    int i,j;
    for (i=1; i<=4; i++)
        for (j=1; j<=4; j++)
            a[i][j]=0;
    a[1][2]=1;
    a[2][3]=1;
    a[3][4]=1;
    a[4][2]=C;
    a[4][3]=B;
    a[4][4]=A;
}
void initializare_rez(int rez[5][5])
{
    int i,j;
    for (i=1; i<=4; i++)
        for (j=1; j<=4; j++)
            rez[i][j]=0;
    rez[1][1]=1;
    rez[2][2]=1;
    rez[3][3]=1;
    rez[4][4]=1;
}
void initializare_ini(int ini[5][5])
{
    int i,j;
    for (i=1; i<=4; i++)
        for (j=1; j<=4; j++)
            ini[i][j]=0;
    ini[1][1]=0;
    ini[2][1]=x;
    ini[3][1]=y;
    ini[4][1]=z;
}
void inmultire(int m1[5][5],int m2[5][5])
{
    int i,j,k;
    for (i=1; i<=4; i++)
        for (j=1; j<=4; j++)
            mrez[i][j]=0;
    for (i=1; i<=4; i++)
        for (j=1; j<=4; j++)
            for (k=1; k<=4; k++)
                mrez[i][j]=(mrez[i][j]+(m1[i][k]*m2[k][j])%666013)%666013;
}
void ridicare_la_putere(int a[5][5],int exp)
{
    int i,j;
    initializare_rez(rez);
    while (exp!=0)
        if (exp%2==0)
        {
            exp=exp/2;
            inmultire(a,a);
            for (i=1; i<=4; i++)
                for (j=1; j<=4; j++)
                    a[i][j]=mrez[i][j];
        }
        else
        {
            exp--;
            inmultire(rez,a);
            for (i=1; i<=4; i++)
                for (j=1; j<=4; j++)
                    rez[i][j]=mrez[i][j];
        }
}
int main()
{
    int n,t,k;
    in>>t;
    for (k=1; k<=t; k++)
    {
        in>>x>>y>>z>>A>>B>>C>>n;
        initializare_a(a);
        ridicare_la_putere(a,n-2);
        initializare_ini(ini);
        inmultire(rez,ini);
        out<<mrez[4][1]<<"\n";
    }
    return 0;
}