#include <stdlib.h>
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string.h>
#define Modulo 666013


using namespace std;

long long matrix[3][3];
long long ident[3][3];
long long prod[3][3];

void mult(long long a[3][3], long long b[3][3])
{
	long long c[3][3];
	long long val = 0;
	for (int i=0;i<3;i++)
		for (int j=0;j<3;j++)
		{
			for (int k=0;k<3;k++)
				val += ( (a[i][k] % Modulo ) * ( b[k][j] % Modulo) % Modulo );
			c[i][j] = val % Modulo;
			val = 0;
		}

	for (int i=0;i<3;i++)
		for (int j=0;j<3;j++)
		{
			prod[i][j] = c[i][j];
		}
}
void init_identity()
{
    for (int i=0;i<3;i++)
    for (int j=0;j<3;j++)
    {
        if (i == j) ident[i][j] = 1;
        else ident[i][j] = 0;
    }
}
void print_matrix(long long a[3][3])
{
    for (int i=0;i<3;i++)
    {

        printf("\n");
            for (int j=0;j<3;j++)
    {
        printf("%d ",a[i][j]);
    }
    }
}
void power(long long p )
{
    for(; p; p/=2)
    {

    if(p%2==1)
    {
        mult(ident,matrix);
        memcpy(ident,prod,sizeof(prod));

    }

    mult(matrix,matrix);
    memcpy(matrix,prod,sizeof(prod));
    }
}

int main(int argc, char *argv[])
{
    long long nr_linii;


	FILE *File1 = fopen("iepuri.in","r");
	FILE *File2 = fopen("iepuri.out","w");
    fscanf(File1,"%lld",&nr_linii);
    long vect[3];


    for (int i = 0;i<nr_linii;i++)
    {

        init_identity();
        for (int i=0;i<3;i++)
        for (int j=0;j<3;j++)
        {
            matrix[i][j] = 0;
        }

        matrix[1][0] = 1;
        matrix[2][1] = 1;

        long zile;
        for (int j = 0;j<3;j++)
        {
          fscanf(File1,"%ld",&vect[j]);
        }

        for (int j = 0;j<3;j++)
        {
          fscanf(File1,"%lld",&matrix[2-j][2]);
        }
        fscanf(File1,"%ld", &zile);
        zile -= 2;
        power(zile);

        long long val = 0;
        for (int j = 0;j<3;j++)
            {
                val += ( (vect[j] % Modulo ) * ( ident[j][2] % Modulo) % Modulo );
            }

        fprintf(File2,"%lld\n",val % Modulo);

    }
    fclose(File1);
    fclose(File2);


	return 0;
}