//
//  main.cpp
//  lgput
//
//  Created by Serban Bantas on 22/02/2020.
//  Copyright © 2020 Serban Bantas. All rights reserved.
//

#include <cstdio>
using namespace std;
const int n_max = 10001; // Definim numarul maxim de cifre al numerelor
const int m = 666013;
long long solo[4][4],M[4][4];
void inmultaa()
{
    long long c[3][3];
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
            c[i][j]=0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                c[i][j] = (c[i][j] + 1LL * M[i][k] * M[k][j]) % m;
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
            M[i][j]=c[i][j];
}
void inmultsola()
{
    long long c[3][3];
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
            c[i][j]=0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                c[i][j] = (c[i][j] + 1LL * solo[i][k] * M[k][j]) % m;
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
            solo[i][j]=c[i][j];
}
void f()
{
//    freopen("kfib.in","r",stdin);
//    freopen("kfib.out","w",stdout);
    long long a,b,c, sol=0,ii[3],n,i,j;
    scanf("%lld%lld%lld%lld%lld%lld%lld",&ii[2],&ii[1],&ii[0],&a,&b,&c,&n);
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            M[i][j]=solo[i][j]=0;
    M[0][0]=a;
    M[0][1]=b;
    M[0][2]=c;
    M[1][0]=M[2][1]=1;
    M[1][1]=M[1][2]=M[2][0]=M[2][2]=0;
    solo[0][0]=solo[1][1]=solo[2][2]=1;
    for (i = 0; (1<<i) <= n; ++ i)  // Luam toti biti lui p la rand
    {
        if ( ((1<<i) & n) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
            inmultsola();
        
        inmultaa(); // Inmultim a cu a ca sa obtinem n^(2^(i+1))
    }
    for(i=0;i<3;++i)
        sol=(sol+solo[2][i]*ii[i])%m;
    printf("%lld\n",sol);
    return;
}
int main()
{
   //    freopen("iepuri.in","r",stdin);
   //    freopen("iepuri.out","w",stdout);
    int t;
    scanf("%d",&t);
    for(;t;--t)
        f();
    return 0;
}