#include <fstream>
#include <iostream>
#include <string>
#include <string.h>
using namespace std;

#define MODULO 666013

const char infile[] = "iepuri.in";
const char outfile[] = "iepuri.out";

class Matrix3
{
public:

	Matrix3()
	{
		memset(&data, 0, sizeof(data));
	}

	Matrix3(int init[3], bool type)
	{
		memset(&data, 0, sizeof(data));
		if(type == true)
		{
			for(int i = 0 ; i < 3; i++)
			{
				data[0][i] = init[i];
			}
		}
		else
		{
			for(int i = 0 ; i < 3; i++)
			{
				data[i][2] = init[i];
			}
			data[1][0] = 1;
			data[2][1] = 1;
		}
	}

	long long* operator[] (int i)
	{
		return &data[i][0];
	}

	Matrix3 power(int power)
	{
		Matrix3 current = *this;
		Matrix3 result;
		for(int i = 0 ; i < 3; i++)
		{
			result[i][i] = 1;
		}
		
		for(int i = 0; i <= 31; i++)
		{
			
			if( (1<<i) & power)
			{
				result = result * current;
			}
			current = current * current;
		}
		return result;
	}

	Matrix3 operator *(Matrix3& other)
	{
		Matrix3 result;
		for(int i = 0; i < 3; i++)
		{
			for(int j = 0; j < 3; j++)
			{
				for(int z = 0; z < 3; z++)
				{
					result[i][j] += (this->data[i][z] * other.data[z][j]) % MODULO;
					result[i][j] %= MODULO;
				}
			}
		}

		return result;
	}

protected:

private:
	long long data[3][3];

};




inline void readVector(int vector[3], istream& stream)
{
	for(int i = 0 ; i < 3; i++)
	{
		stream >> vector[i];
	}
}

inline void readVectorReverse(int vector[3], istream& stream)
{
	for(int i = 2 ; i>= 0; i--)
	{
		stream >> vector[i];
	}
}

void solve()
{
	fstream fin(infile, ios::in);
	fstream fout(outfile, ios::out);

	int questionCount;

	fin >> questionCount;

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

		int xyz[3];
		int abc[3];
		int n;

		readVector(xyz, fin);
		readVectorReverse(abc, fin);
		
		fin >> n;

		Matrix3 matrixXYZ(xyz, true);
		Matrix3 matrixABC(abc, false);

		matrixABC = matrixABC.power(n-2);
		matrixXYZ = matrixXYZ * matrixABC;
		fout << matrixXYZ[0][2] << "\n";

	}

	fin.close();
	fout.close();
}





int main(int argc, char* argv[])
{
	solve();
}