#include <fstream>
#define MOD 666013
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
long long I[4][4],rez[4],b[4][4],cop[4][4];
void inmultesc(long long a[4][4], long long b[4][4])
{
    int i,j,k;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            for(k=1;k<=3;k++)
                cop[i][j]=(cop[i][j]+a[i][k]*b[k][j])%MOD;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        {
            a[i][j]=cop[i][j];
            cop[i][j]=0;
        }
}
void ridic(long long a[4][4],long long b[4][4],int c)
{
    if(c>0)
    {
        if((c&1)==0)///par
        {
            inmultesc(a,a);
            ridic(a,b,c/2);
        }
        else
        {
            inmultesc(b,a);
            ridic(a,b,c-1);
        }
    }
}
int main()
{
    int t,n,i,j;
    cin>>t;
    while(t>0)
    {
        t--;
        b[1][1]=1;
        b[2][2]=1;
        b[3][3]=1;
        cin>>rez[1]>>rez[2]>>rez[3]>>I[3][3]>>I[3][2]>>I[3][1]>>n;
        I[1][2]=1;
        I[2][3]=1;
        ridic(I,b,n-2);
        cout<<((1LL*b[3][1]*rez[1])%MOD+(1LL*b[3][2]*rez[2])%MOD+(1LL*b[3][3]*rez[3])%MOD)%MOD<<'\n';
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
            {
                I[i][j]=0;
                b[i][j]=0;
            }
    }
    return 0;
}