import sys, math
sys.setrecursionlimit(1000000)
INF = 1 << 100
mod = 1000000007
#mod = 998244353
input = lambda: sys.stdin.readline().rstrip()
li = lambda: list(map(int, input().split()))

def s(n):
    return (1+n)*n //2

def f(n):
    return n*(n+1)*(2*n + 1) //6
t = int(input())


ans = []
for _ in range(t):
    N, M = li()
    x = pow(N, M, mod)
    y = pow(N, M//2, mod)
    ans.append((s(x) - f(y)) % mod)

print(*ans, sep='\n')