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)