#include <cstdio>
#define MOD 666013

using namespace std;

int a[5][5], m[5][5], rez[5][5];
int k;
int x, y, z, A, B, C, n, t;

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


void inmultire(int a[5][5], int m[5][5])
{
    int c[5][5];
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            int s=0;
            for(int k=1; k<=3; k++)
                s+=((1LL*a[i][k]*m[k][j])%MOD);
            c[i][j]=s%MOD;
        }
    }
    copiere(a, c);
}


void put(int p)
{
    copiere(rez, m);
    p--;
    while(p>0)
    {
        if(p%2==1)
        {
            p--;
            inmultire(rez, m);
            //copiere(a, rez);
        }
        p/=2;
        inmultire(m, m);
    }

}

void zerozare(int a[5][5])
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            a[i][j]=0;
}

int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    scanf("%d", &t);
    for(int i=1;i<=t;i++)
    {
        scanf("%d %d %d %d %d %d %d", &x, &y, &z, &A, &B, &C, &n);
        a[1][1]=z;
        a[1][2]=y;
        a[1][3]=x;
        m[1][1]=A;
        m[2][1]=B;
        m[3][1]=C;
        m[1][2]=1;
        m[2][3]=1;
        put(n-2);
        inmultire(a, rez);
        printf("%d\n", a[1][1]);
        zerozare(a);
        zerozare(m);
        zerozare(rez);
    }


    return 0;
}