#include <iostream>
#include <fstream>
#define MOD  666013
using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
short t;
int x,y,z,a,b,c,n;
unsigned long long mab[4][4],mac[4][4],mar[4][4];
int main()
{
    fin>>t;

    for(;t;t--)
    {

        mab[1][1]=mab[1][2]=mab[2][2]=mab[3][1]=0;
        mab[2][1]=mab[3][2]=1;
        fin>>x>>y>>z>>mab[3][3]>>mab[2][3]>>mab[1][3]>>n;
        n=n-2;
        ///mac=I3;
        mac[1][1]=mac[2][2]=mac[3][3]=1;
        mac[1][2]=mac[1][3]=mac[2][1]=mac[2][3]=mac[3][1]=mac[3][2]=0;

        ///mod
        ///fout<<mab[1][1]<<" "<<mab[1][2]<<" "<<mab[1][3]<<endl<<mab[2][1]<<" "<<mab[2][2]<<" "<<mab[2][3]<<endl<<mab[3][1]<<" "<<mab[3][2]<<" "<<mab[3][3]<<endl;


        for(int i=0;(1<<i)<=n;i++)
        {
            if(n&(1<<i))
            {
                ///mar=mac*mab;
                mar[1][1]=((mac[1][1]*mab[1][1])%MOD+(mac[1][2]*mab[2][1])%MOD+(mac[1][3]*mab[3][1])%MOD)%MOD;
                mar[1][2]=((mac[1][1]*mab[1][2])%MOD+(mac[1][2]*mab[2][2])%MOD+(mac[1][3]*mab[3][2])%MOD)%MOD;
                mar[1][3]=((mac[1][1]*mab[1][3])%MOD+(mac[1][2]*mab[2][3])%MOD+(mac[1][3]*mab[3][3])%MOD)%MOD;
                mar[2][1]=((mac[2][1]*mab[1][1])%MOD+(mac[2][2]*mab[2][1])%MOD+(mac[2][3]*mab[3][1])%MOD)%MOD;
                mar[2][2]=((mac[2][1]*mab[1][2])%MOD+(mac[2][2]*mab[2][2])%MOD+(mac[2][3]*mab[3][2])%MOD)%MOD;
                mar[2][3]=((mac[2][1]*mab[1][3])%MOD+(mac[2][2]*mab[2][3])%MOD+(mac[2][3]*mab[3][3])%MOD)%MOD;
                mar[3][1]=((mac[3][1]*mab[1][1])%MOD+(mac[3][2]*mab[2][1])%MOD+(mac[3][3]*mab[3][1])%MOD)%MOD;
                mar[3][2]=((mac[3][1]*mab[1][2])%MOD+(mac[3][2]*mab[2][2])%MOD+(mac[3][3]*mab[3][2])%MOD)%MOD;
                mar[3][3]=((mac[3][1]*mab[1][3])%MOD+(mac[3][2]*mab[2][3])%MOD+(mac[3][3]*mab[3][3])%MOD)%MOD;

                ///mac=mar;
                mac[1][1]=mar[1][1];
                mac[1][2]=mar[1][2];
                mac[1][3]=mar[1][3];
                mac[2][1]=mar[2][1];
                mac[2][2]=mar[2][2];
                mac[2][3]=mar[2][3];
                mac[3][1]=mar[3][1];
                mac[3][2]=mar[3][2];
                mac[3][3]=mar[3][3];

            }

            ///mr=mab*mab;
            mar[1][1]=((mab[1][1]*mab[1][1])%MOD+(mab[1][2]*mab[2][1])%MOD+(mab[1][3]*mab[3][1])%MOD)%MOD;
            mar[1][2]=((mab[1][1]*mab[1][2])%MOD+(mab[1][2]*mab[2][2])%MOD+(mab[1][3]*mab[3][2])%MOD)%MOD;
            mar[1][3]=((mab[1][1]*mab[1][3])%MOD+(mab[1][2]*mab[2][3])%MOD+(mab[1][3]*mab[3][3])%MOD)%MOD;
            mar[2][1]=((mab[2][1]*mab[1][1])%MOD+(mab[2][2]*mab[2][1])%MOD+(mab[2][3]*mab[3][1])%MOD)%MOD;
            mar[2][2]=((mab[2][1]*mab[1][2])%MOD+(mab[2][2]*mab[2][2])%MOD+(mab[2][3]*mab[3][2])%MOD)%MOD;
            mar[2][3]=((mab[2][1]*mab[1][3])%MOD+(mab[2][2]*mab[2][3])%MOD+(mab[2][3]*mab[3][3])%MOD)%MOD;
            mar[3][1]=((mab[3][1]*mab[1][1])%MOD+(mab[3][2]*mab[2][1])%MOD+(mab[3][3]*mab[3][1])%MOD)%MOD;
            mar[3][2]=((mab[3][1]*mab[1][2])%MOD+(mab[3][2]*mab[2][2])%MOD+(mab[3][3]*mab[3][2])%MOD)%MOD;
            mar[3][3]=((mab[3][1]*mab[1][3])%MOD+(mab[3][2]*mab[2][3])%MOD+(mab[3][3]*mab[3][3])%MOD)%MOD;
            ///mab=mr;
            mab[1][1]=mar[1][1];
            mab[1][2]=mar[1][2];
            mab[1][3]=mar[1][3];
            mab[2][1]=mar[2][1];
            mab[2][2]=mar[2][2];
            mab[2][3]=mar[2][3];
            mab[3][1]=mar[3][1];
            mab[3][2]=mar[3][2];
            mab[3][3]=mar[3][3];

        }
        fout<<((x*mac[1][3])%MOD+(y*mac[2][3])%MOD+(z*mac[3][3])%MOD)%MOD<<'\n';
    }
    return 0;
}