def solve():
    mod = 10 ** 9 + 7
    n, m = map(int,input().split())
    x = pow(n, m, mod)
    y = pow(n, m // 2, mod)
    ans = x * (x + 1) * pow(2, mod - 2, mod) - y * (2 * y + 1) * (y + 1) * pow(6, mod - 2, mod)
    ans %= mod
    return ans

t = int(input())
ans = []
for _ in range(t):
    ans.append(solve())

for i in ans:
    print(i)