#include <fstream>
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
int q;
int a,b,C,x,y,z;
const int M=666013;
long long n,f[1][3],r[1][3],masca[3][3],puteri[3][3],c[3][3];
void inmultire(long long a[][3],long long b[][3])
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            c[i][j]=0;
            for(int d=0;d<3;d++)
                c[i][j]=(c[i][j]%M+a[i][d]*b[d][j]*1LL%M)%M;
        }
        for(int i=0;i<3;i++)
           for(int j=0;j<3;j++)
                a[i][j]=c[i][j];

}
void exponentiere(int n)
{
    if(n==0)
    {
        for(int i=0;i<3;i++)
           puteri[i][i]=1;
        return;
    }
    exponentiere(n/2);
    inmultire(puteri,puteri);
    if(n%2==1)
       inmultire(puteri,masca);
}
int main()
{
    cin>>q;
    for(int i=0;i<q;i++)
    {
    cin>>x>>y>>z;
    cin>>a>>b>>C;
    cin>>n;
    masca[0][2]=C;
    masca[1][2]=b;
    masca[2][2]=a;
    masca[1][0]=1;
    masca[2][1]=1;
    f[0][0]=x;
    f[0][1]=y;
    f[0][2]=z;
    for(int i=0;i<3;i++)
      for(int j=0;j<3;j++)
         puteri[i][j]=0;
    exponentiere(n);
    r[0][0]=0;
    r[1][0]=0;
    r[2][0]=0;
    for(int i=0;i<1;i++)
        for(int j=0;j<3;j++)
            for(int d=0;d<3;d++)
                 r[i][j]=(r[i][j]%M+f[i][d]*puteri[d][j]*1LL%M)%M;
         cout<<r[0][0]<<'\n';
    }

    return 0;
}