#include <bits/stdc++.h>
#define N 3
#define mod 666013

using namespace std;

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

struct matrix
{
    int m[N][N];
    matrix operator * (matrix B)
    {
        matrix C;
        memset(C.m,0,sizeof(C.m));
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                for(int k=0;k<N;k++)
                    C.m[i][j]=(C.m[i][j]+(m[i][k]*B.m[k][j])%mod)%mod;
        return C;
    }
}unit,null;

matrix exp(matrix A, int p)
{
    matrix rez=unit;
    while(p)
    {
        if(p & 1)
        {
            rez=rez*A;
            p--;
        }
        else
        {
            A=A*A;
            p=p/2;
        }
    }
    return rez;
}

int main()
{
    int t;
    in>>t;
    memset(unit.m,0,sizeof(unit.m));
    memset(null.m,0,sizeof(null.m));
    for(int i=0;i<N;i++)
        unit.m[i][i]=1;
    for(;t>0;t--)
    {
        int x,y,z,a,b,c,n;
        in>>x>>y>>z>>a>>b>>c>>n;
        matrix A={z,y,x,0,0,0,0,0,0};
        matrix B={a,1,0,b,0,1,c,0,0};
        B=exp(B,n-2);
        A=A*B;
        out<<A.m[0][0]<<'\n';
    }
    return 0;
}