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 sys
  input = lambda : sys.stdin.readline().rstrip()
  
  sys.setrecursionlimit(2*10**5+10)
  write = lambda x: sys.stdout.write(x+"\n")
  debug = lambda x: sys.stderr.write(x+"\n")
  writef = lambda x: print("{:.12f}".format(x))
  
  
  ### 素数の逆元とCombination
  
  M = 10**9+7 # 出力の制限
  # M = 998244353
  N = 2*10**5+10 # 必要なテーブルサイズ
  g1 = [0] * (N+1) # 元テーブル
  g2 = [0] * (N+1) #逆元テーブル
  inverse = [0] * (N+1) #逆元テーブル計算用テーブル
  g1[0] = g1[1] = g2[0] = g2[1] = 1
  inverse[0], inverse[1] = [0, 1] 
  for i in range( 2, N + 1 ):
      g1[i] = ( g1[i-1] * i ) % M 
      inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
      g2[i] = (g2[i-1] * inverse[i]) % M 
  def cmb(n, r, M=M):
      if ( r<0 or r>n ):
          return 0
      r = min(r, n-r)
      return ((g1[n] * g2[r] % M) * g2[n-r]) % M
  def perm(n, r, M=M):
      if (r<0 or r>n):
          return 0
      return (g1[n] * g2[n-r]) % M
  def sub(n,k):
      ans = 0
      for v in range(1<<k):
          for v2 in range(1<<k):
              if v&v2>=v^v2:
                  ans += 1
      return ans
  def sub3(n,k):
      ans = 0
      for v in range(1<<k):
          for v2 in range(1<<k):
              for v3 in range(1<<k):
                  if v&v2&v3>=v^v2^v3:
                      ans += 1
      return ans
  
  def sub2(n,k):
      val = 0
      for i in range(0,n+1,2):
          val += cmb(n,i)
          if val>M:
              val -= M
      if k==0:
          ans = 1
      else:
          if n%2==1:
              ans = pow(1+val, k, M)
          else:
              ans = 0
              v = 1
              v2 = pow(2, n*(k-1), M)
              inv = pow(pow(2, n, M), M-2, M)
              for i in range(k):
                  ans += v * v2 % M
                  v *= (val-1)
                  v%= M
                  v2 *= inv
                  v2 %= M
                  if ans>M:
                      ans -= M
              ans += pow(val-1, k, M)
      return ans
  t = int(input())
  res = []
  for _ in range(t):
      n,k = list(map(int, input().split()))
      ans = sub2(n,k)
      res.append(ans%M)
  #     print(val)
  write("\n".join(map(str, res)))