#include<stdio.h>
#include<string.h>

int t;
long w[5],n;
int a,b,c;

void prelucrare()
{
for (int i=3; i<=n; i++)
    {
    w[3]=w[2]*a+w[1]*b+w[0]*c;
    w[0]=w[1];
    w[1]=w[2];
    w[2]=w[3];
    }
}

void scriere()
{
long q;
q=w[3]%666013;
printf("%lu\n",q);
}

void citire()
{
freopen("iepuri.in","r",stdin);
scanf("%d",&t);
for (int i=1; i<=t; i++)
    {
    memset(w,0,sizeof(w));
    scanf("%lu",&w[0]);
    scanf("%lu",&w[1]);
    scanf("%lu",&w[2]);
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    scanf("%lu",&n);
    prelucrare();
    scriere();
    }
fclose(stdin);
}

int main()
{
freopen("iepuri.out","w",stdout);
citire();
fclose(stdout);
return 0;
}