#include <cstdio>
#include <fstream>
#include <cstring>
#define m 666013
using namespace std;
void prd (int a[4][4],int b[4][4]){
    int c[4][4];
    memset(c,0,sizeof(c));
    for(int k=1;k<=3;++k)
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
    c[k][i]=(c[k][i]+1ll*a[k][j]*b[j][i])%m;
    memcpy(a,c,sizeof(c));
}
int main (){
    int a[4][4],b[4][4],t,n,x,y,z,i,v[64];
    ifstream in ("iepuri.in");
    freopen ("iepuri.out","w",stdout);
    for(in>>t;t;--t){
        memset(a,0,sizeof(a));
        in>>x>>y>>z>>a[1][1]>>a[1][2]>>a[1][3]>>n;
        a[2][1]=a[3][2]=1,n-=2;
        memcpy(b,a,sizeof(a));
        for(i=0;n;n>>=1)
            v[++i]=n%2;
        for(--i;i;--i){
            prd(a,a);
            if(v[i])
                prd(a,b);
            }
        printf("%lld\n",(1ll*z*a[1][1]%m+1ll*y*a[1][2]%m+1ll*x*a[1][3])%m);
    }
    return 0;}