#include<fstream>
#define M 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int r[5][5],s[5][5],t,x,y,z,a,b,c,n,v[5],f[5],k[5][5];
void ve()
{
    int p;
    while(n)
    {
        p=1;
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                s[i][j]=0;
        s[1][1]=a;
        s[2][1]=b;
        s[3][1]=c;
        s[1][2]=1;
        s[2][3]=1;
        while(1)
        {
            if(1LL*2*p>n)
                break;
            for(int i=1;i<=3;i++)
                for(int j=1;j<=3;j++)
                {
                    k[i][j]=s[i][j];
                    s[i][j]=0;
                }
            p=2*p;
            for(int i=1;i<=3;i++)
                for(int j=1;j<=3;j++)
                    for(int h=1;h<=3;h++)
                        s[i][j]=(s[i][j]+1LL*k[i][h]*k[h][j])%M;
        }
        n-=p;
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
            {
                k[i][j]=r[i][j];
                r[i][j]=0;
            }
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                for(int h=1;h<=3;h++)
                    r[i][j]=(r[i][j]+1LL*k[i][h]*s[h][j])%M;
    }
}
int main()
{
    fin>>t;
    for(int h=1;h<=t;h++)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        n-=2;
        f[1]=z;
        f[2]=y;
        f[3]=x;
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                r[i][j]=0;
        for(int i=1;i<=3;i++)
            r[i][i]=1;
        ve();
        v[1]=v[2]=v[3]=0;
        for(int j=1;j<=3;j++)
            for(int h=1;h<=3;h++)
                v[j]=(v[j]+1LL*f[h]*r[h][j])%M;
        fout<<v[1]<<'\n';
    }
}