"""
平方数以外
"""


MOD = 10 ** 9 + 7

def solve():
    n, m = map(int, input().split())
    x = pow(n, m, MOD)
    ans = x * (x + 1) // 2
    x = pow(n, m // 2, MOD)
    ans -= x * (x + 1) * (2 * x + 1) // 6
    print(ans % MOD)


for _ in range(int(input())):
    solve()