mod = 10 ** 9 + 7
div2 = pow(2, mod-2, mod)
div6 = pow(6, mod-2, mod)


def main():
    N, M = map(int, input().split())
    m = M // 2

    x = pow(N, M, mod)
    y = pow(N, m, mod)

    res = x * (x + 1) % mod * div2 % mod
    res -= y * (y + 1) % mod * (2 * y + 1) % mod * div6 % mod
    return res % mod


T = int(input())
for _ in range(T):
    print(main())