#include<bits/stdc++.h>
using namespace std;

ifstream in("iepuri.in");
ofstream out("iepuri.out");
#define MOD 666013
int ziua1,ziua2,ziua3,m1,m2,m3;
int n;


struct matrix
{
    long long mat[4][4];

    matrix(int diagonal)
    {
        for(int i=0; i<4; i++)
        {
            for(int k=0; k<4; k++)
            {
                if(i==k)
                    mat[i][k]=diagonal;
                else
                    mat[i][k]=0;

            }

        }
    }


    matrix operator*(matrix&other)
    {
        matrix result(0);
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
            {
                for(int k=0; k<4; k++)
                {
                    result.mat[i][j]=(result.mat[i][j]+mat[i][k]*other.mat[k][j])%MOD;
                }
            }
        }
        return result;
    }

    void prt()
    {
        for(int i=0; i<4; i++)
        {
            for(int k=0; k<4; k++)
                cout<<mat[i][k]<<" ";
            cout<<endl;
        }
    }


};

void multiply(matrix&a,long long*b)
{
    int result[4] {0,0,0,0};

    for(int i=0; i<4; i++)
    {
        for(int k=0; k<4; k++)
        {
            result[i]=(result[i]+a.mat[i][k]*b[k])%MOD;
        }
    }
    for(int i=0; i<4; i++)
        b[i]=result[i];


}


void read_new_set()
{
    in>>ziua1>>ziua2>>ziua3>>m1>>m2>>m3>>n;
}


matrix fast_exponentiation(matrix a,int pow)
{
    matrix x=a;
    matrix result(1);
    for(long long i=1; i<=pow; i=i<<1)
    {
        if(pow&i)
        {
            result=result*x;
        }
        x=x*x;
    }
    return result;
}

int main()
{
    int t;
    in>>t;

    for(int i=0; i<t; i++)
    {
        read_new_set();
        long long b[4] {(ziua1*m3+ziua2*m2+ziua3*m1)%MOD,ziua3,ziua2,ziua1};
        if(n==3)
        {
            out<<b[0]<<'\n';
        }
        else
        {
            matrix a(0);
            a.mat[0][0]=m1;
            a.mat[0][1]=m2;
            a.mat[0][2]=m3;
            a.mat[1][0]=1;
            a.mat[2][1]=1;
            a.mat[3][2]=1;

            a=fast_exponentiation(a,n-3);

            multiply(a,b);
            out<<b[0]<<'\n';
        }


    }

    return 0;
}