#include <fstream>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");

long long i,j,t,a,b,c,x,y,z,n,p,rez[3][3],m1[3][3],m2[3][3],m3[3][3];

void prod()
{
    int i,j;
    for (i=0; i<3; i++)
    for (j=0; j<3; j++)
        m1[i][j]=(m2[i][0]*m3[0][j]+m2[i][1]*m3[1][j]+m2[i][2]*m3[2][j])%666013;
}

void calc()
{
    int i,j;
    for (i=0; i<3; i++)
    for (j=0; j<3; j++)
        rez[i][j]=0;
    for (i=0; i<3; i++)
    for (j=0; j<3; j++)
        m1[i][j]=0;
    rez[1][0]=1; rez[2][1]=1; rez[0][2]=c; rez[1][2]=b; rez[2][2]=a;
    n-=3;
    while (n>0)
    {
        for (i=0; i<3; i++)
        for (j=0; j<3; j++)
            m1[i][j]=0;
        m1[1][0]=1; m1[2][1]=1; m1[0][2]=c; m1[1][2]=b; m1[2][2]=a;
        p=1;
        while (p*2<=n)
        {
            p*=2;
            for (i=0; i<3; i++)
            for (j=0; j<3; j++)
                m2[i][j]=m1[i][j];
            for (i=0; i<3; i++)
            for (j=0; j<3; j++)
                m3[i][j]=m1[i][j];
            prod();
        }
        for (i=0; i<3; i++)
        for (j=0; j<3; j++)
            m2[i][j]=rez[i][j];
        for (i=0; i<3; i++)
        for (j=0; j<3; j++)
            m3[i][j]=m1[i][j];
        prod();
        for (i=0; i<3; i++)
        for (j=0; j<3; j++)
            rez[i][j]=m1[i][j];
        n-=p;
    }
    g << (x*rez[0][2]+y*rez[1][2]+z*rez[2][2])%666013 << "\n";
}

int main()
{
    f >> t;
    for (;t--;)
    {
        f >> x >> y >> z >> a >> b >> c >> n;
        calc();
    }
}