import sys

# Constanta modulo din enunț
MOD = 666013

def mul(A, B):
    # Dimensiunile matricelor
    rows_A = len(A)
    cols_A = len(A[0])
    cols_B = len(B[0])
    
    C = [[0] * cols_B for _ in range(rows_A)]
    for i in range(rows_A):
        for k in range(cols_A):
            if A[i][k] == 0: continue  # Optimizare pt viteza in Python
            for j in range(cols_B):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

def power(A, p):
    # Matricea identitate I3
    res = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    while p > 0:
        if p % 2 == 1:
            res = mul(res, A)
        A = mul(A, A)
        p //= 2
    return res

def helper(x, y, z, a, b, c, n):
    # Cazuri de baza
    if n == 0: return x % MOD
    if n == 1: return y % MOD
    if n == 2: return z % MOD
    
    # Matricea de tranzitie bazata pe recurenta R_n = a*R_{n-1} + b*R_{n-2} + c*R_{n-3}
    # [R_{n-2}, R_{n-1}, R_n] = [R_{n-3}, R_{n-2}, R_{n-1}] * C
    C = [
        [0, 0, c],
        [1, 0, b],
        [0, 1, a]
    ]
    
    # Ridicam la puterea (n-2) pentru a ajunge de la [x, y, z] la [..., ..., R_n]
    C_n = power(C, n - 2)
    
    # Rezultatul Rn este x*C_n[0][2] + y*C_n[1][2] + z*C_n[2][2]
    ans = (x * C_n[0][2] + y * C_n[1][2] + z * C_n[2][2]) % MOD
    return ans

def solve():
    # Citim tot odata pentru viteza
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    T = int(input_data[0])
    results = []
    for i in range(T):
        # Fiecare test are 7 parametri
        base = 1 + i * 7
        x = int(input_data[base])
        y = int(input_data[base+1])
        z = int(input_data[base+2])
        a = int(input_data[base+3])
        b = int(input_data[base+4])
        c = int(input_data[base+5])
        n = int(input_data[base+6])
        results.append(str(helper(x, y, z, a, b, c, n)))
    
    # Printam toate rezultatele separate prin newline
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()