mod = 10**9 + 7
for _ in range(int(input())):
	N, M = map(int, input().split())
	ans = 0
	pNM = pow(N, M, mod)
	pNM2 = pow(N, M // 2, mod)
	ans += pNM * (pNM + 1) // 2 % mod
	ans -= pNM2 * (pNM2 + 1) * (2 * pNM2 + 1) // 6 % mod
	ans %= mod
	print(ans)