import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INV2 = pow(2, -1, MOD)
INV6 = pow(6, -1, MOD)

t = int(input())
for _ in [0] * t:
    n, m = map(int, input().split())
    x = pow(n, m, MOD)
    y = pow(n, m // 2, MOD)
    ans = INV2 * x % MOD * (x + 1) % MOD
    ans = (ans - INV6 * y % MOD * (y + 1) % MOD * (2 * y + 1) % MOD) % MOD
    print(ans)