import sys input = sys.stdin.readline mod = 10**9+7 T = int(input()) for _ in range(T): N, M = map(int, input().split()) x = pow(N, M, mod) ans = x*(x+1)*pow(2, mod-2, mod) y = pow(N, M//2, mod) ans -= y*(y+1)*(2*y+1)*pow(6, mod-2, mod) print(ans % mod)