mod = 10**9+7
t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    limit = pow(n,m,mod)
    i = pow(n,m//2,mod)
    ans = limit * (limit + 1) // 2 % mod
    ans -= i*(i+1)*(2*i+1)//6 % mod
    print(ans%mod)