#include<bits/stdc++.h>
#define cnt 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long long zile, a[4][4], b[4][4], c[4][4], A, B, C, x, y, z, quiz;

void expo(long long power)
{
    int i, j, k, l, p = 1;
    for(i=1; i<=3; i++)
        for(j=1; j<=3; j++)
            if(i == j)
                b[i][j] = 1;
            else
                b[i][j] = 0;
    for(l=0; p<=power; l++)
    {
        if((p & power) > 0)
        {
            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] + (b[i][k] * a[k][j])%cnt) % cnt;
                }
            for(i=1; i<=3; i++)
                for(j=1; j<=3; j++)
                    b[i][j] = c[i][j] % cnt;
        }
        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] * a[k][j]) % cnt) % cnt;
            }
        for(i=1; i<=3; i++)
            for(j=1; j<=3; j++)
                a[i][j] = c[i][j] % cnt;
        p = p * 2;
    }
}
int main()
{
    fin >> quiz;
    for(int p=1; p<=quiz; p++)
    {
        fin >> x >> y >> z >> A >> B >> C >> zile;
        if(zile > 2)
        {
            a[1][1] = 0;
            a[1][2] = 0;
            a[1][3] = C;
            a[2][1] = 1;
            a[2][2] = 0;
            a[2][3] = B;
            a[3][1] = 0;
            a[3][2] = 1;
            a[3][3] = A;
            expo(zile-2);
            fout << ((x * b[1][3]) % cnt + (y * b[2][3]) % cnt + (z * b[3][3]) %cnt) % cnt;
            fout << '\n';
        }
        if(zile == 0)
            fout << x << '\n';
        if(zile == 1)
            fout << y << '\n';
        if(zile == 2)
            fout << z << '\n';
    }
    fout.close();
    return 0;
}