T = int(input()) mod = 10 ** 9 + 7 inv2 = pow(2,mod-2,mod) inv6 = pow(6,mod-2,mod) def sum2(st,goal,n): return ((st + goal) * n) % mod * inv2 def sum3(n): return (n * (n+1) * (2 * n + 1)) % mod * inv6 ANS = [] for _ in range(T): N,M = map(int,input().split()) ans = sum2(1,pow(N,M,mod),pow(N,M,mod)) - sum3(pow(N,M//2,mod)) ANS.append(ans%mod) print(*ANS,sep='\n')