#include <fstream>
#define prim 666013
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
void fib(int k);
int n,t,test,x,y,z,a,b,c,i,j;
int m[4][4];
int s[4][4];
int main()
{
    cin>>t;
    for(test=1; test<=t; test++)
    {
        for(i=1; i<=3; i++)
        {
            for(j=1; j<=3; j++)
            {
                m[i][j]=0;
            }
        }
        cin>>x>>y>>z>>a>>b>>c>>n;
        if(n==0) cout<<x<<'\n';
        if(n==1) cout<<y<<'\n';
        if(n==2) cout<<z<<'\n';
        else
        {
            fib(n-2);
            /*for(i=1;i<=3;i++)
                {for(j=1;j<=3;j++)
                cout<<m[i][j]<<" ";
            cout<<'\n';}*/
            cout<<((m[3][1]*x)%prim+(m[3][2]*y)%prim+(m[3][3]*z)%prim)%prim<<'\n';
        }
    }
}
void fib(int k)
{
    if(k==1)
    {
        m[1][1]=0;m[1][2]=1;m[1][3]=0;
        m[2][1]=0;m[2][2]=0;m[2][3]=1;
        m[3][1]=c;m[3][2]=b;m[3][3]=a;
    }
    else
    {
        fib(k/2);
        for(int i=1; i<=3; i++)
            for(int j=1; j<=3; j++)
            {
                s[i][j]=m[i][j];
            }
        int sum,l;
        for(int i=1; i<=3; i++)
            for(int j=1; j<=3; j++)
            {
                sum=0;
                for(l=1; l<=3; l++)
                {
                    sum+=(s[i][l]*s[l][j])%prim;
                }
                m[i][j]=sum%prim;
            }
        if(k%2==1)
        {
            for(int i=1; i<=3; i++)
                for(int j=1; j<=3; j++)
                {
                    s[i][j]=m[i][j];
                }
        m[1][1]=(c*s[1][3])%prim;m[1][2]=(s[1][1]+b*s[1][3])%prim;m[1][3]=(s[1][2]+a*s[1][3])%prim;
        m[2][1]=(c*s[2][3])%prim;m[2][2]=(s[2][1]+b*s[2][3])%prim;m[2][3]=(s[2][2]+a*s[2][3])%prim;
        m[3][1]=(c*s[3][3])%prim;m[3][2]=(s[3][1]+b*s[3][3])%prim;m[3][3]=(s[3][2]+a*s[3][3])%prim;

        }
    }
}