#include <bits/stdc++.h>

using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

const int64_t MOD=666013;

class Matrix
{
public:
    int64_t x[4][4]={{0},{0},{0},{0}};
    int64_t* operator[](int i) {return x[i];}
    friend Matrix operator * (Matrix A,Matrix B)
    {
        Matrix res;
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                for(int k=1;k<=3;k++)
                    res[i][j]=(res[i][j]+A[i][k]*B[k][j])%MOD;
        return res;
    }
    friend Matrix operator^(Matrix A,int p)
    {
        if(p==1) return A;
        if(p&1)  return A*(A^(p-1));
        Matrix X=A^(p/2);
        return X*X;
    }
};

int F[4],A,B,C;
int Fib(int n)
{
	Matrix M;
	M[1][1]=0,M[1][2]=1,M[1][3]=0;
	M[2][1]=0,M[2][2]=0,M[2][3]=1;
	M[3][1]=C,M[3][2]=B,M[3][3]=A;
	if(n==1) return 1;
	M=M^n;
	int64_t res=0;
	for(int i=1;i<=3;i++) res=(res+M[1][i]*F[i])%MOD;
	return res;

}

main()
{
	for(int n,t=(f>>t,t);t--;)
		f>>F[1]>>F[2]>>F[3]>>A>>B>>C>>n,
		g<<Fib(n)<<'\n';
}