#include <fstream>

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