#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

int x,y,z,a1,b1,c1,n,t;


void show(int c[3][3]){
    int i,j;
    for(i=0;i<3;++i){
        for(j=0;j<3;++j) cout<<c[i][j]<<' ';
    cout<<'\n';
    }
    cout<<"------------\n";
}


void mult(int a[3][3],int b[3][3], int c[3][3]){
    int i,j,k;
    //memset(a,0,sizeof(a));

    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            a[i][j]=0;

    show(a);
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            for(k=0;k<3;++k)
            a[i][j]+=b[i][k]*c[k][j];
}

void set(int a[3][3], int c[3][3]){
    int i,j;
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            a[i][j]=c[i][j];
}


int solve(){
    int a[3][3],b[3][3],c[3][3];
    a[0][0]=0; a[0][1]=0; a[0][2]=c1;
    a[1][0]=1; a[1][1]=0; a[1][2]=b1;
    a[2][0]=0; a[2][1]=1; a[2][2]=a1;

    memset(c,0,sizeof(c));
    c[0][0]=1; c[1][1]=1; c[2][2]=1;
    show(c);

  //  mult(b,c,a);
  //  set(c,b);
    int p=n-2,i;

    for(i=0; (1<<i)<=p; ++i){
       if( (1<<i) & p ){
            mult(b,c,a);
            set(c,b);
            show(c);
       }
       mult(b,a,a);
       set(a,b);
    }

    return (x*c[0][2]+y*c[1][2]+z*c[2][2])%666013;

}
int main(){
    ifstream fin("iepuri.in");
    ofstream fout("iepuri.out");
    fin>>t;
    for(int i=1;i<=t;++i){
        fin>>x>>y>>z>>a1>>b1>>c1>>n;
        fout<<solve()<<'\n';
    }
    return 0;
}