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)