#include<fstream.h>
long long T,x,y,z,A,B,C,N,a[2000000],S;
long long suma(long N){
for (long i=2;i<N;i++)               {
    a[i+1]=a[i]*A+a[i-1]*B+a[i-2]*C;
    S+=a[i];}

return a[N]%666013;}
int main(){
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
fin>>T;
for (long i=0;i<T;i++) {
    fin>>a[0]>>a[1]>>a[2]>>A>>B>>C>>N;
    fout<<suma(N);
    fout<<"\n";}
return 0;
}