#include <fstream>
#define MOD 666013
using namespace std;
ifstream cin ("iepuri.in");
ofstream cout ("iepuri.out");
int v[]= {3,2,2,2,1,1,1,2,2,1};
long long m1[12][12],n,t,a,b,c,x,y,z;
void inmultire(long long m1[12][12], long long m2[12][12])
{
    long long rez[12][12]= {0};
    for(int i=0; i<=2; i++)
    {
        for(int j=0; j<=2; j++)
        {
            for(int k=0; k<=2; k++)
                rez[i][j]=(rez[i][j]+1LL*m1[i][k]*m2[k][j])%MOD;
        }
    }
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            m1[i][j]=rez[i][j];
}
void inmultire2(int m1[12], long long int m2[12][12])
{
    long long x[4]={0};
    for(int j=0; j<=2; j++)
        for(int k=0; k<=2; k++)
            x[j]=(x[j]+1LL*m1[k]*m2[k][j])%MOD;
    cout<<x[2]<<'\n';
}
void exponentiere(long long int m1[12][12],int a)
{
    long long rez[12][12]= {0};
    for(int i=0; i<=2; i++)
        rez[i][i]=1;
    while(a)
    {
        if(a%2==1)
        {
            inmultire(rez,m1);
        }
        inmultire(m1,m1);
        a=a/2;
    }
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            m1[i][j]=rez[i][j];
}
int main()
{
    cin>>t;
    while(t)
    {
        cin>>x>>y>>z>>a>>b>>c>>n;
        m1[0][0]=0;
        m1[1][0]=1;
        m1[2][0]=0;
        m1[0][1]=0;
        m1[1][1]=0;
        m1[2][1]=1;
        m1[0][2]=c;
        m1[1][2]=b;
        m1[2][2]=a;
        v[0]=x;
        v[1]=y;
        v[2]=z;
        exponentiere(m1,n-2);
        inmultire2(v,m1);
        t--;
    }
    return 0;
}