T = int(input())
P = 10 ** 9 + 7
def calc(n,m):
    N = n
    M = m
    u = pow(N,M,P)
    ans = u * (u + 1) // 2 % P
    v = pow(N,M // 2,P)
    tmp = v * (v + 1) * (2 * v + 1) // 6
    return (ans - tmp) % P
for _ in range(T):
    n,m = map(int,input().split())
    print(calc(n,m))