import sys
input = sys.stdin.readline
from collections import *

MOD = 10**9+7
inv = lambda x: pow(x, MOD-2, MOD)

for _ in range(int(input())):
    N, M = map(int, input().split())
    x = pow(N, M, MOD)
    y = pow(N, M//2, MOD)
    print((x*(1+x)*inv(2)%MOD-y*(y+1)*(2*y+1)*inv(6)%MOD)%MOD)