import sys

def mul(A, B):
    rows_A, cols_A = len(A), len(A[0])
    rows_B, cols_B = len(B), len(B[0])
    if cols_A != rows_B:
        print("Compabtilbity error")
        return -1
    C = [[0] * cols_B for _ in range(rows_A)]
    for row_A in range(rows_A):
        for col_B in range(cols_B):
            sum1 = 0
            for k in range(cols_A):
                sum1 = (sum1 + A[row_A][k] * B[k][col_B]) % 666013
            C[row_A][col_B] =  sum1
    return C
    
def pow(A, n):
    if n == 1:
        return A
    if n % 2 == 0:
        D = pow(A, n//2)
        return mul(D, D)
    else:
        return mul(pow(A, n - 1), A)
    

def helper(x,y,z,a,b,c,n):
    if n == 2:
        return z
    if n == 1:
        return y
    if n == 0:
        return x
    C = [[0] * 3 for _ in range(3)]
    C[1][0] = 1
    C[2][1] = 1
    C[0][2] = c
    C[1][2] = b
    C[2][2] = a

    n -= 2

    S = [[x, y, z]]

    res = mul(S, pow(C, n))

    return res[-1][-1]

def solve():
    data =  list(map(int, sys.stdin.read().split()))
    T = data[0]
    for i in range(T):
        x, y, z = data[7 * i + 1], data[7 * i + 2], data[7 * i + 3]
        a, b, c = data[7 * i + 4], data[7 * i + 5], data[7 * i + 6]
        n = data[7 * i + 7]
        print(helper(x,y,z,a,b,c,n))

if __name__ == "__main__":
    solve()