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

def f2(n):
    return n * (n + 1) * (2 * n + 1) // 6

MOD = 10 ** 9 + 7
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    print((f(pow(n, m, MOD)) - f2(pow(n, m // 2, MOD))) % MOD)