//#include <iostream>
#include <cstdio>
#define in "iepuri.in"
#define out "iepuri.out"
#define M 666013
using namespace std;
int t,x,y,z,a,b,c,n;
void solve(){
  int i,f,aux,auxx;
  f = z;
  for(i = 3; i <= n; i++)
  {
     f = ((a*z)%M+(b*y)%M+(c*x)%M)%M;
     auxx=y;
     aux = z;
     z = f;
     y = aux;
     x = auxx;
  }
  printf("%d\n",f);
}
int main(){
    int i;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;i++){
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        solve();
    }
    return 0;
}