#include <fstream>

using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
long long rez[4][4],aux[4][4],m[4][4];
int main()
{
    int a,b,c,t,n,i,j,k;
    long long x,y,z;
    cin>>t;
    while(t>0)
    {
        t--;
        cin>>x>>y>>z>>a>>b>>c>>n;
        n-=2;
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
                {
                    rez[i][j]=0;
                    m[i][j]=0;
                }
        rez[1][1]=1;
        rez[2][2]=1;
        rez[3][3]=1;
        m[1][2]=1;
        m[2][3]=1;
        m[3][1]=c;
        m[3][2]=b;
        m[3][3]=a;
        while(n>0)
        {
            if((n&1)==0)///par
            {
                for(i=1;i<=3;i++)
                    for(j=1;j<=3;j++)
                        for(k=1;k<=3;k++)
                            aux[i][j]=(aux[i][j]+m[i][k]*m[k][j])%666013;
                for(i=1;i<=3;i++)
                    for(j=1;j<=3;j++)
                    {
                        m[i][j]=aux[i][j];
                        aux[i][j]=0;
                    }
                n=n>>1;
            }
            else///impar
            {
                for(i=1;i<=3;i++)
                    for(j=1;j<=3;j++)
                        for(k=1;k<=3;k++)
                            aux[i][j]=(aux[i][j]+m[i][k]*rez[k][j])%666013;
                for(i=1;i<=3;i++)
                    for(j=1;j<=3;j++)
                    {
                        rez[i][j]=aux[i][j];
                        aux[i][j]=0;
                    }
                n--;
            }
        }
        cout<<(rez[3][1]*x+rez[3][2]*y+rez[3][3]*z)%666013<<'\n';
    }
    return 0;
}