#include<iostream.h>
#include<stdio.h>
int main()
{ long n, w, x, y, z;
  int  a, b, c, t, i, j;
  freopen("iepuri.in", "rt", stdin);
  freopen("iepuri.out", "wt", stdout);
  cin>>t;
  for(i=1;i<=t;i++)
  { cin>>x>>y>>z>>a>>b>>c>>n;
    for(j=3;j<=n;j++)
    { w=c*x+b*y+a*z;
      x=y;
      y=z;
      z=w;
    }
  z=z%666013;
  cout<<z<<endl;
  }
  return 0;
}