#include <fstream>
#include <cstring>
#define R 666013
using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

typedef long long unsigned ull;
ull A[4][4],B[4][4],cop[4][4];

void multiplication(ull V[4][4],ull W[4][4])
{
    ull mat[4][4];
    memset(mat,0,sizeof(mat));
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)mat[i][j]+=(V[i][k]*W[k][j])%R;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)V[i][j]=mat[i][j]%R;
}

void power(ull K)
{
    while(K)
    {
        if(K%2==1)
        {
            multiplication(cop,B);
            K--;
        }else{
            multiplication(B,B);
            K/=2;
        }
    }
}

int main()
{
    int T,x,y,z,a,b,c,n;
    fin>>T;
    for(;T;T--)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(cop,0,sizeof(cop));
        cop[1][1]=cop[2][2]=cop[3][3]=1;
        A[1][1]=x;
        A[1][2]=y;
        A[1][3]=z;
        B[2][1]=B[3][2]=1;
        B[1][3]=c;
        B[2][3]=b;
        B[3][3]=a;
        power(n-2);
        multiplication(A,cop);
        fout<<A[1][3]%R<<'\n';
    }
    return 0;
}