#include <fstream>

using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
int t,u,i,k,c,j,y[4],o,v[45],z;
long long rez;
struct MAT{long long a[4][4];};
MAT a,fa,e,b;
void prod(MAT a,MAT b,MAT &c)
{
     int i,j,z;
     for (i=1;i<=3;i++)
          for (j=1;j<=3;j++)
          {
              c.a[i][j]=0;
              for (z=1;z<=3;z++)
              c.a[i][j]+=a.a[i][z]*b.a[z][j],c.a[i][j]=c.a[i][j]%666013;
          }
}
int main()
{
    f>>t;
    for (u=1;u<=t;u++)
    {
        rez=0;
        for (i=1;i<=3;i++)
        f>>y[i];
        for (i=1;i<=3;i++)
        f>>a.a[1][i];
        a.a[2][1]=a.a[3][2]=1;
        f>>k;
        c=k-2;
        o=-1;
        while(c>=1)
        {
           v[++o]=c%2;
           c=c/2;
        }
        for (i=1;i<=3;i++)
             for (j=1;j<=3;j++)
             if (i!=j) e.a[i][j]=0;
            else e.a[i][i]=1;
        for (i=0;i<=o;i++)
        if (v[i]==1)
        {
            fa=a;
            for (j=1;j<=i;j++)
            {
                prod(fa,fa,b);
                fa=b;
            }
            prod(e,fa,b);
            e=b;
        }
        for (i=1;i<=3;i++)
        rez+=e.a[1][i]*y[3-i+1];
        rez=rez%666013;
        g<<rez<<'\n';
    }
    return 0;
}