description: Moamen and Ezzat are playing a game. They create an array a of n non-negative integers where every element is less than 2^k.
  
  Moamen wins if a_1  \&  a_2  \&  a_3  \&  …  \&  a_n ≥ a_1 ⊕ a_2 ⊕ a_3 ⊕ … ⊕ a_n.
  
  Here \& denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND), and ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
  
  Please calculate the number of winning for Moamen arrays a.
  
  As the result may be very large, print the value modulo 1 000 000 007 (10^9 + 7).
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 5)— the number of test cases. 
  
  Each test case consists of one line containing two integers n and k (1 ≤ n≤ 2⋅ 10^5, 0 ≤ k ≤ 2⋅ 10^5).
  
  Output
  
  For each test case, print a single value — the number of different arrays that Moamen wins with.
  
  Print the result modulo 1 000 000 007 (10^9 + 7).
  
  Example
  
  Input
  
  
  3
  3 1
  2 1
  4 0
  
  
  Output
  
  
  5
  2
  1
  
  Note
  
  In the first example, n = 3, k = 1. As a result, all the possible arrays are [0,0,0], [0,0,1], [0,1,0], [1,0,0], [1,1,0], [0,1,1], [1,0,1], and [1,1,1].
  
  Moamen wins in only 5 of them: [0,0,0], [1,1,0], [0,1,1], [1,0,1], and [1,1,1].
solution: import queue
  from math import *
  import sys
  from collections import *
  from random import *
  
  sys.setrecursionlimit(99999)
  eps = sys.float_info.epsilon
  P = 31
  MOD = 10**9+7
  
  def is_prime(n):
      if n == 0 or n == 1:
          return False
      d = 2
      while d * d <= n:
          if n % d == 0:
              return False
          d += 1
      return True
  
  
  def div_up(n, k):
      if n % k == 0:
          return n // k
      else:
          return n // k + 1
  
  
  def bfs(start, visited, graph):
      q = deque()
      visited[start] = True
      q.appendleft(start)
      while len(q) != 0:
          v = q.pop()
          for to in graph[v]:
              if not visited[to]:
                  visited[to] = True
                  q.appendleft(to)
  
  
  def to_int(c):
      if c == '>':
          return 0
      return 1
  
  
  def ford_bellman(edges, d, cost, n):
      for i in range(n - 1):
          flag = True
          for edge in edges:
              v, u = edge[0], edge[1]
              temp = d[v] + cost[edge]
              if temp < d[u]:
                  d[u] = temp
                  flag = False
          if flag:
              break
  
  
  def num_len(n, base):
      if n == 0:
          return 1
      return int(floor(log(n, base) + 1))
  
  
  cycles = 0
  def dfs(graph, cl, p, v):
      global cycles
      cl[v] = 1
      for to in graph[v]:
          if cl[to] == 1 and p[v] != to:
              cycles += 1
          elif cl[to] == 0:
              p[to] = v
              dfs(graph, cl, p, to)
      cl[v] = 2
  
  
  def down(a):
      for i in range(1, len(a)):
          if a[i] > a[i - 1]:
              return False
      return True
  
  
  def up(a):
      for i in range(1, len(a)):
          if a[i] < a[i - 1]:
              return False
      return True
  
  
  def _hash_(s):
      res = 0
      for i in range(len(s)):
          res += (ord(s[i]) - ord('a')) * P**i
      return res
  
  
  def binpow(a, n):
      res = 1
      while n:
          if n & 1:
              res *= a
              res %= MOD
          a *= a
          a %= MOD
          n >>= 1
      return res
  
  
  def solve():
      n, k = map(int, input().split())
      S = binpow(2, n - 1)
      if k == 0:
          print(1)
          return
      eq = S
      if n % 2 != 0:
          eq += 1
      else:
          eq -= 1
      prev = 0
      if n % 2 == 0:
          prev += 1
      dp_big_1 = prev
      x = binpow(2, n)
      y = eq
  
      for i in range(2, k + 1):
          prev = (prev * x + y * dp_big_1) % MOD
          y = (y * eq) % MOD
      print((binpow(eq, k) + prev) % MOD)
  
  
  for _ in range(int(input())):
      solve()
  
  
  def debug():
      pass
  
  # debug()
  