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

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

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

void scriere()
{
printf("%lu",w[n]%666013);
}

void citire()
{
freopen("iepuri.in","r",stdin);
scanf("%d",t);
for (int i=1; i<=n; 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;
}