#include <cstdio>
const int R = 666013;
int x,y,z,a,b,c,n;
int m[3][3];
void atrib_i3(int m[][3])
{
    for (int i = 0; i <= 2; ++i)
        for (int j = 0 ; j <= 2; ++j)
			if(i==j)
				m[i][j]=1;
			else
				m[i][j]=0;
}

void inmultire(int a[][3], int b[][3], int r[][3])
{
    for (int i = 0; i <= 2; ++i)
        for (int j = 0; j <= 2; ++j)
        {
            r[i][j] = 0;
            for (int k = 0; k <= 2; ++k)
                r[i][j] += ((long long)a[i][k] * b[k][j])%R;
            r[i][j] = r[i][j]%R;
        }
}
void putere(int m[][3], int n, int r[][3])
{
    int a[3][3];
    if (n == 0)
    {
        atrib_i3(r);
        return;
    }
    if (n % 2 == 0)
    {
        putere(m,n/2,a);
        inmultire(a,a,r);
    }
    else
    {
        putere(m,n-1,a);
        inmultire(a,m,r);
    }
}
void rezolva()
{
    int r[3][3];
    m[2][0] = c;
    m[2][1] = b;
    m[2][2] = a;
    putere(m,n-2,r);
    printf("%d\n",((long long)r[2][0] * x + (long long)r[2][1] * y + (long long)r[2][2] * z) % R);
}

int main()
{
    int t;
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    m[0][0] = 0;
    m[0][1] = 1;
    m[0][2] = 0;
    m[1][0] = 0;
    m[1][1] = 0;
    m[1][2] = 1;
    for (int i = 1; i <= t; ++i)
    {
        scanf("%d %d %d %d %d %d %d",&x,&y,&z,&a,&b,&c,&n);
        rezolva();
    }
}