#include <bits/stdc++.h>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
struct matrice{
long long a[5][5];
matrice(){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        a[i][j]=0;
    }
};
matrice inmmat(matrice a,matrice b){
    matrice r;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    for(int k=1;k<=3;k++){
        r.a[i][j]+=a.a[i][k]*b.a[k][j];
    }
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    r.a[i][j]%=666013;
    return r;
}
void afis(matrice a){
 for(int i=1;i<=3;i++,cout<<endl)
    for(int j=1;j<=3;j++)
        cout<<a.a[i][j]<<" ";
}
matrice matput(matrice x,int b){
    if(b==1)
        return x;
    if(b%2==0)
        return matput(inmmat(x,x),b/2);
    return inmmat(x,matput(inmmat(x,x),b/2));
}
int main()
{
    int t;
   fin>>t;
   for(;t--;){
        int x,y,z,a,b,c,putere;
        fin>>x>>y>>z>>a>>b>>c>>putere;
        matrice v,f;
        v.a[1][1]=x;
        v.a[1][2]=y;
        v.a[1][3]=z;
        f.a[2][1]=f.a[3][2]=1;
        f.a[1][3]=c;
        f.a[2][3]=b;
        f.a[3][3]=a;
        putere-=2;
        f=matput(f,putere);
        f=inmmat(v,f);
    //afis(f);
    fout<<f.a[1][3]<<"\n";
   }
}