#include <stdio.h>
using namespace std;

int t;
long long int n;
long int i, j, k, h; 
int d[10001];
int nrd;
long long int m[4][4], p[4][4], l[4][2], rez[4][2], aux[4][4];
long long int x, y, z;
int a, b, c;

int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    scanf("%d", &t);
    for ( h = 1; h <= t; h++ )
    {
        scanf("%lld %lld %lld", &x, &y, &z);
        scanf("%d %d %d", &a, &b, &c);
        scanf("%lld", &n);
        m[1][1] = m[1][3] = m[2][1] = m[2][2] = 0;
        m[1][2] = m[2][3] = 1;
        m[3][1] = c;
        m[3][2] = b;
        m[3][3] = a;
        l[1][1] = x;
        l[2][1] = y;
        l[3][1] = z;
        i = n;
        nrd = 0;
        while ( i )
        {
            nrd++;
            d[nrd] = i % 2;
            i /= 2;
        }
        for ( i = 1; i <= 3; i++ )
            for ( j = 1; j <= 3; j++ )
            {
                if ( i == j ) p[i][j] = 1;
                else          p[i][j] = 0;
                rez[i][1] = 0;
            }    
        for ( int ba = 1; ba <= nrd; ba++ )
        {
            if ( d[ba] )
            {
                for ( i = 1; i <= 3; i++ )
                    for ( j = 1; j <= 3; j++ )
                        aux[i][j] = 0;
                for ( i = 1; i <= 3; i++ )
                    for ( j = 1; j <= 3; j++ )
                        for ( k = 1; k <= 3; k++ )
                            aux[i][j] = (aux[i][j] + (p[i][k]*m[k][j])%666013)%666013;
                for ( i = 1; i <= 3; i++ )
                    for ( j = 1; j <= 3; j++ )
                        p[i][j] = aux[i][j];
            }
            for ( i = 1; i <= 3; i++ )
                for ( j = 1; j <= 3; j++ )
                    aux[i][j] = 0;
            for ( i = 1; i <= 3; i++ )
                for ( j = 1; j <= 3; j++ )
                    for ( k = 1; k <= 3; k++ )
                        aux[i][j] = (aux[i][j] + (m[i][k]*m[k][j])%666013)%666013;                
            for ( i = 1; i <= 3; i++ )
                for ( j = 1; j <= 3; j++ )
                    m[i][j] = aux[i][j];
        }
        for ( i = 1; i <= 3; i++ )
            for ( k = 1; k <= 3; k++ )
                rez[i][1] = (rez[i][1] + (p[i][k]*l[k][1])%666013)%666013;
        printf("%d\n", rez[1][1]);    
    }
    return 0;
}