#include<fstream>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long long matr[4][4];
int i,j,m=666013,t;
long long c,b,a,x,y,z,n;
void inmultire(long long a[4][4], long long b[4][4])
{
    long long c[4][4];
    int i,j,k;
    for(i=1;i<=3;i++)
    {
        for(j=1;j<=3;j++)
        {
            c[i][j]=0;
            for(k=1;k<=3;k++)
            {
                c[i][j]=(c[i][j]%m+a[i][k]*b[k][j]%m)%m;
            }
        }
    }
    for(i=1;i<=3;i++)
    {
        for(j=1;j<=3;j++)
        {
            a[i][j]=c[i][j];
        }
    }
}
void lgput(long long p[4][4], int n)
{
    int i;
    long long matr[4][4];
    for(i=1;i<=3;i++)
    {
        for(j=1;j<=3;j++)
        {
            if(j==i)
            {
                p[i][j]=1;
            }
            else
            {
                p[i][j]=0;
            }
        }
    }
    matr[1][1]=matr[1][3]=matr[2][1]=matr[2][2]=0;
    matr[1][2]=matr[2][3]=1;
    matr[3][1]=c;
    matr[3][2]=b;
    matr[3][3]=a;
    while(n!=0)
    {
        if((n&1)==1)
        {
            inmultire(p,matr);
        }
        inmultire(matr,matr);
        n=n>>1;
    }
}
int main()
{
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        lgput(matr,n-2);
        fout<<(x*matr[3][1]%m+y*matr[3][2]%m+z*matr[3][3]%m)%m<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}