#include<fstream>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
unsigned long long t,x,y,z,a,b,c,n,i,j,v[4],w[4];
int main(){
    fin>>t;
    for(i=1;i<=t;i++){
        fin>>x>>y>>z>>a>>b>>c>>n;
        v[1]=x%666013;
        v[2]=y%666013;
        v[3]=z%666013;
        for(j=1;j<=n-2;j++){
            w[3]=(v[1]*c)%666013+(v[2]*b)%666013+(v[3]*a)%666013;
            v[1]=v[2]%666013;
            v[2]=v[3]%666013;
            v[3]=w[3]%666013;
        }
        fout<<v[3]<<"\n";

    }
    return 0;
}