MOD = 666013
def iepuri(x, y, z, a, b, c, n):
    dp = [0] * (n + 1)
    dp[0] = x
    dp[1] = y
    dp[2] = z
    for i in range(3, n + 1):
        dp[i] = a * dp[i - 1] + b * dp[i - 2] + c * dp[i - 3]
    return dp[n]

def mat_mul(A, B):
    C = [[0]*3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

def mat_pow(M, p):
    R = [[1,0,0],[0,1,0],[0,0,1]]
    while p > 0:
        if p % 2 == 1:
            R = mat_mul(R, M)
        M = mat_mul(M, M)
        p = p // 2
    return R

def iepuri2(x, y, z, a, b, c, n):
    dp = [0] * (n + 1)
    dp[0] = x
    dp[1] = y
    dp[2] = z

    A = [[a, b, c],
         [1, 0, 0],
         [0, 1, 0]]
    
    M = mat_pow(A, n - 2)

    # V3 = [z, y, x]
    res = (M[0][0] * z + M[0][1] * y + M[0][2] * x) % MOD
    return res

with open("iepuri.in") as f, open("iepuri.out", "w") as g:
    k = int(f.readline())
    for i in range(k):
        x, y, z, a, b, c, n = map(int, f.readline().split())
        g.write(str(iepuri2(x, y, z, a, b, c, n)) + "\n")