#include <bits/stdc++.h>
#define nmax 666013
using namespace std;

int t,x1, x2, x3, a, b, c;





void prod1(long long a1[4][4], long long b1[4][4]) {



	long long c[4][4];
	int i, j;

	for(i = 1;i <= 3; i++) {
		for(j = 1; j <= 3; j++) {

					c[i][j] = (a1[i][1] * b1[1][j])%nmax;
					c[i][j] = (c[i][j] + (a1[i][2] * b1[2][j])%nmax)%nmax;
					c[i][j] = (c[i][j] + (a1[i][3] * b1[3][j])%nmax)%nmax;
			 }
	}
	for(i = 1; i <= 3 ;i++ ) {
		for( j = 1; j <= 3; j++ ) {

			 a1[i][j] = c[i][j];
		}
	}

}
 

int main() {

freopen("iepuri.in", "r", stdin);
freopen("iepuri.out", "w", stdout);
scanf("%d",&t);
int r, r1, i;
long long  j,mult[4][4], a1[4][4], a2[4][4];
int y;
for(int y = 1; y <= t;y++) {
	scanf("%d %d %d %d %d %d %d", &x1, &x2, &x3, &a, &b, &c, &r);
	  
	  

        
	 	for(i = 1; i <= 3; ++i)
        for(j = 1; j <= 3; ++j)
        {
            a1[i][j]=0;
        }
        a1[3][1] = c;
        a1[3][2] = b;
        a1[3][3] = a;
        a1[1][2] = 1;
        a1[2][3] = 1;


        if (r&1) 
	
			 {
			 	for(i = 1; i <= 3; ++i)
        for(j = 1; j <= 3; ++j)
        {
            a2[i][j]=0;
        }
        a2[3][1] = c;
        a2[3][2] = b;
        a2[3][3] = a;
        a2[1][2] = 1;
        a2[2][3] = 1;
			 }
	
		else
	
		       	 {

		       	 		 	for(i = 1; i <= 3; ++i)
        for(j = 1; j <= 3; ++j)
        {
            a2[i][j]=0;
        }
		       	 	for(i=1;i<=3;i++) {
		       	 		for(j=1;j<=3;j++) {
		       	 			if(i == j)
		       	 				a2[i][j] = 1;
		       	 		}
		       	 	}
		       	 }
 
	
		for (j=2;j<=r;j=j<<1) {
	
			prod1(a1,a1);
	
 
	
			if (r&j) 
	
				prod1(a2,a1);
	
		}
	
 

        long long  t1;
        t1 = (a2[1][1]*x1)%nmax;
        t1 = (t1 + (a2[1][2]*x2)%nmax)%nmax; 
        t1 = (t1 + (a2[1][3]*x3)%nmax)%nmax;
         


	printf("%lld\n",t1);
}



	return 0;
}