#include <fstream>
using namespace std;
#define m 666013
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int n,t,x,y,z,a,b,c;
long long A[4][4],B[4][4],C[4][4];

int main()
{
    fin>>t;
    for(int k=1;k<=t;k++)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        A[1][1]=A[1][2]=A[2][2]=A[3][1]=B[1][1]=B[1][2]=B[2][2]=B[3][1]=0;
        A[1][3]=B[1][3]=a;
        A[2][3]=B[2][3]=b;
        A[3][3]=B[3][3]=c;
        n-=2;
        for(int u=1;u<=n;u++)
        {
            for(int i=1;i<=3;i++)
            {
                for(int j=1;j<=3;j++)
                {
                    C[i][j]=0;
                    for(int f=1;f<=3;f++)
                    {
                        C[i][j]+=(A[i][f]*B[f][j])%m;
                    }
                }
            }
            for(int i=1;i<=3;i++)
            {
                for(int j=1;j<=3;j++)
                {
                    A[i][j]=C[i][j]%m;
                }
            }
        }
        fout<<((A[1][3]*z)%m+(A[2][3]*y)%m+(A[3][3]*x)%m)%m<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}