#include<fstream>
#define mod 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
long long m[4][4],o[4][4],aux[4][4],x,y,z,a,b,c,n,rez;
int main()
{
    int i,j,r;
    f>>r;
    while(r)
    {
        f>>a>>b>>c;
        f>>m[1][1]>>m[1][2]>>m[1][3];
        f>>n;
        m[2][2]=m[2][3]=m[3][1]=m[3][3]=0;
        o[1][2]=o[1][3]=o[2][1]=o[2][3]=o[3][1]=o[3][2]=0;
        o[1][1]=o[2][2]=o[3][3]=1;
        m[2][1]=m[3][2]=1;
        n-=2;
        while(n)
        {
            if(n%2!=0)
            {
                for(i=1;i<=3;i++)
                  for(j=1;j<=3;j++)
                    aux[i][j]=(o[i][1]*m[1][j]+o[i][2]*m[2][j]+o[i][3]*m[3][j])%mod;
                for(i=1;i<=3;i++)
                  for(j=1;j<=3;j++)
                    o[i][j]=aux[i][j];
            }
            for(i=1;i<=3;i++)
              for(j=1;j<=3;j++)
                aux[i][j]=(m[i][1]*m[1][j]+m[i][2]*m[2][j]+m[i][3]*m[3][j])%mod;
            for(i=1;i<=3;i++)
              for(j=1;j<=3;j++)
                m[i][j]=aux[i][j];
            n/=2;
        }
        rez=((o[1][1]*c)%mod+(o[1][2]*b)%mod+(o[1][3]*a)%mod)%mod;
        g<<rez<<"\n";
        r--;
    }
    return 0;
}