mod=10**9+7
def f1(x):
  return (x*(x+1)//2)%mod

def f2(x):
  return (x*(x+1)%mod)*(2*x+1)%mod*pow(6,mod-2,mod)%mod

for t in range(int(input())):
  N,M=map(int,input().split())
  print((f1(pow(N,M,mod))-f2(pow(N,M//2,mod)))%mod)