#include <stdio.h>
 
using namespace std;
 
FILE*f=fopen("iepuri.in","r"),*g=fopen("iepuri.out","w");
 
int t, m[5][5], in[5][5], sol[2][5];
 
void inmultire_insusi()
{
    int aux[4][4];
    for(int i = 1; i <= 3; i++)
    {
        for(int k = 1; k <= 3; k++)
        {
            int s = 0;
            for(int j = 1; j <= 3; j++)
            {
                s += (in[i][j] * in[j][k]) % 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()
{
    int aux[4][4];
    for(int i = 1; i <= 3; i++)
    {
        for(int k = 1; k <= 3; k++)
        {
            int s = 0;
            for(int j = 1; j <= 3; j++)
            {
                s += (in[i][j] * m[j][k]) % 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(int 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();
 
}
 
int inmultire_valoare()
{
    int 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",&t);
    int x, y, z, a, b, c, n;
    m[2][1] = 1;
    m[3][2] = 1;
    for(int i = 1; i <= t; i ++)
    {
        fscanf(f,"%d %d %d %d %d %d %d",&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);
        int sum = inmultire_valoare();
        fprintf(g,"%d\n",sum);
 
    }
    return 0;
}