S = int(input())
div2 = pow(2, mod-2, mod)
for _ in range(S):
    N, M, X = map(int, input().split())

    if X == 0:
        ans = (pow(1 - M, N, mod) + pow(1 + M, N, mod)) * div2 % mod
    else:
        ans = (pow(1 + M, N, mod) - pow(1 - M, N, mod)) * div2 % mod
    print(ans)