#include <bits/stdc++.h>
#define for_(i,f,t) for(int i=f;i<=t;i++)
#define assign(M,r,a,b,c) M[r][1]=a,M[r][2]=b,M[r][3]=c

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_(i,1,3) for_(j,1,3) for_(k,1,3)
            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;
	assign(M,1, 0,1,0);
	assign(M,2, 0,0,1);
	assign(M,3, C,B,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';
}