#include <stdio.h>

using namespace std;

FILE*f=fopen("iepuri.in","r"),*g=fopen("iepuri.out","w");

int t;
long long m[5][5], in[5][5], sol[2][5];

void inmultire_insusi()
{
    long long aux[4][4];
    for(int i = 1; i <= 3; i++)
    {
        for(int k = 1; k <= 3; k++)
        {
            long long s = 0;
            for(int j = 1; j <= 3; j++)
            {
                s += (in[i][j] * in[j][k]);
                s %= 666013;
            }
            aux[i][k] = s;
        }
    }
    for(int i = 1; i <= 3; i++)
    {
        for(int j = 1; j <= 3; j++)
        {
            in[i][j] = aux[i][j];
        }
    }

}
void inmultire_m()
{
    long long aux[4][4];
    for(int i = 1; i <= 3; i++)
    {
        for(int k = 1; k <= 3; k++)
        {
            long long s = 0;
            for(int j = 1; j <= 3; j++)
            {
                s += (in[i][j] * m[j][k]);
                s %= 666013;
            }
            aux[i][k] = s;
        }
    }
    for(int i = 1; i <= 3; i++)
    {
        for(int j = 1; j <= 3; j++)
        {
            in[i][j] = aux[i][j];
        }
    }
}

void ridicare(long long nr)
{
    if(nr == 0)
    {
        in[1][1] = 1; in[1][2] = 0; in[1][3] = 0;
        in[2][2] = 1; in[2][1] = 0; in[2][3] = 0;
        in[3][3] = 1; in[3][2] = 0; in[3][1] = 0;
        return;
    }
    ridicare(nr/2);
    if(nr % 2 == 1)
    {
        inmultire_insusi();
        inmultire_m();
    }
    else inmultire_insusi();

}

long long inmultire_valoare()
{
    long long s = 0;
    for(int j = 1; j <= 3; j++)
    {
        s = (s + in[1][j] * sol[j][1]) % 666013;
    }
    return s;
}

int main()
{
    fscanf(f,"%d\n",&t);
    int x, y, z, a, b, c;
    long long n;
    m[2][1] = 1;
    m[3][2] = 1;
    for(int i = 1; i <= t; i ++)
    {
        fscanf(f,"%d %d %d %d %d %d %lld\n",&x, &y, &z, &a, &b, &c, &n);
        m[1][1] = a;
        m[1][2] = b;
        m[1][3] = c;
        sol[1][1] = z;
        sol[2][1] = y;
        sol[3][1] = x;
        ridicare(n-2);
        long long sum = inmultire_valoare();
        fprintf(g,"%lld\n",sum);

    }
    return 0;
}