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: """RANK1ZEN; 3966 PEAK; NA; FLEX SUPPORT: Zen, Bap; Battlenet ID -> Knuckles#11791"""
  # region ---------------------------------------------------------------------------|
  # MNNNNNNNNNNNNNNNNMNho///++//+oooooossssssssssssysssooyyyyyso+//++//shNNNNNNNNNNNNNM
  # MNNNNNNNNNNNNNNMNy////////++++oooooooooossssssssoosssssysyyysoossss+/oshNNNNNNNNNNM
  # MNNNNNNNNNNNNMNs///////+oooooo++++oooooooooooso+ossssssssssssssssssss++soymMNNNNNNM
  # MNNNNNNNNNNNMd/:-//+//shNNmhsoo+++++++++ooooo++oooooooooossssssssssssso+ooosmNNNNNM
  # MNNNNNNNNNNMh::://+/+ymMMMMmhsoso+++++++++o+/+ooooooooooooooooooooossso++o+++hMNNNM
  # MNNNNNNNNNMy//-:/+/osmMMMMNhssyshNdssoooo++:++++++++++oooooooooooooooooo++-++/sMMNM
  # MNNNNNNNNMd:/:///+/ohNMMMNhsohyyNMNNNdhhs+:++++++++++++++++++++ooooooooo/+.o+:/+NNM
  # MNNNNNNNMm/:/-///++ooshmmhs+sysdMMMMNdMMd/+++++ooo++++++++++++++++++++++::-++/:/sNM
  # MNNNNNNMN/://-+++++++++oo+//yosNMNMNmNMNo/o/oshNmhyoo+++++++++++++++++++/-/+++:/:sM
  # MNNNNNMNo://-/+++++:/+++++//++osyhmdhMNs/o/+shMMMMmsooooyo++/+++++++++++://+++://oM
  # MNNNNNMs:///:/++++//++-/+/:++++++ooooyo++o-oyNNMMmysooymmso/+shysyyysooo+/++o+/-s+M
  # MNNNNMd:///+:/++++-++:`++:/++++//++++++:+-/oyhsmys+oohmyo++:sNMdmMMNNysy+-ohNs+-myM
  # MNNNMN::///+-:+++:.+/``++/++++++++++++:+/`+++oo/:/++oyo+oy+odNddMMMMmyyh:-sdMh/odyN
  # MNNNNo:///++-:+o/`::```++/+++++++++++//+-.o++:-:/++/+/+ymo/+ossyyhdhssy+.:ohhd/sy+M
  # MMNMh-///+++--oo:`/````++-+++++++++++-o/`/+:.:/+++//+hmNo/++++++ooooooo-`/+o++/++-M
  # MMMN/:///+++-.o/````-s:+/:++++++++++/++`.:.-/++++/+sdmmo/+++++++++++++: -+++++////M
  # MMMh:///++++-`+:```/dN+/::++++++++++++:``.+ooo++ohNMNm++oooooooo+++++o+ :++++/-//oM
  # MMd:/-/+++++-`/.``:hmm//./+++++++++o/o..:osoooymmdddmoooooooooooooo+oms.+++++////+M
  # MMo// -+++++:`.`` dNddo-.:+++++++++++--/soo:.--::ymh+ssssssssssooo+sNN/++++++++/-dM
  # Md/// `/+++o/```` dMddN.-:++++++++++/`/o/+:``-:-`/ooyssssssssssssoodmMo++++++++//NM
  # M/:// `-+oooo.``` oMNMM+--/+++++++++/:yd-``.`-+o+hoyyoosyyyyyyys:+o+o++o//+++++/hMM
  # m++:/```:oooo/````.dmNNm/-/+++++++//+dhy::ohs:/hysyosyyyyyyyyys:----:-/o/ooo++/-mMM
  # s:++//```/oooo-  ``yNmdm:-/++++++////MMNmdhoys+ssssyyyyyysoysss:-.odd/o+/+oo++-+MMM
  # s`:++/````:oooo. ```:hNNh-/++++++//:hNNNMMNMdsossyyyyyyss+osdM/o/:yNyoo///ooo/.MMNM
  # d `-++/-```:+oo+-`````-+ds/++++++//-mMMMNNhs+syyysysyys+osdMMNyoshdh/+/o:ooo+.+MMNM
  # M/` `-/+/-``.:ooo-```````s:++++++++/mNdhsoossssyyhyo/-+hmMMMMNNNNNNo//+.:oo++ oMMNM
  # MMo``:..-//-.`-+oo:.`````/+++++++++:ooossyhyyyo+:-:ohNMmMMMMMNmNNNh:/:` :oo/: mMMNM
  # MMMh.oMh+``.-:-.-/o+-````mh/+++++++:++++/:--:+syhmMMMMMNMMMMMMMMMo-.//``+oo:`-MMNNM
  # MMMMh-omNd+````..`./+/.`hMMs+++++++/dmmmmNMMNNMMMMMMMMMMMMMMMMms:`` :/..+oo: yMNNNM
  # MNNNMN/``..``````````.-.+dNy-oooooo/o+s++sNMMNmNMMmmNMMMMMMMmo-   ``-/.-oo+- yMNNNM
  # MNNNNMMNdy-``````..``````-+o/+ooooo/++///:`:yMMMMMMMMMMMMds/`/++/````o--o++- MMNNNM
  # MMNNMMMMMN:`........-:+oyssoo+ssssss:ooo+/+:`:mMMMMMNho/.````+ooohd+//:+ooo-/MMMMMM
  # MMMMMMMMMMs.-...-.-osyyyyysdMhshhhhhossssssdh-.ss+/-.``----.sdhy+mMMMsosssy:sMMMMMM
  # endregion ------------------------------------------------------------------------|
  # region ---------------------------------------------------------------------------|
  from sys import stdin, stdout, setrecursionlimit
  from bisect import bisect_left, bisect_right
  from math import ceil, floor, log, gcd, sqrt, factorial
  from collections import Counter, deque
  from heapq import heappush, heappop, heapify
  def re(): return stdin.readline().rstrip()
  def ints(): return map(int, stdin.readline().split())
  def test(cases):
      for _ in range(cases): solve()
  mod = 1000000007
  # endregion
  # region ---------------------------------------------------------------------------|
  MOD=10**9+7
  class Factorial:
      def __init__(self, MOD):
          self.MOD = MOD
          self.factorials = [1, 1]
          self.invModulos = [0, 1]
          self.invFactorial_ = [1, 1]
   
      def calc(self, n):
          if n <= -1:
              print("Invalid argument to calculate n!")
              print("n must be non-negative value. But the argument was " + str(n))
              exit()
          if n < len(self.factorials):
              return self.factorials[n]
          nextArr = [0] * (n + 1 - len(self.factorials))
          initialI = len(self.factorials)
          prev = self.factorials[-1]
          m = self.MOD
          for i in range(initialI, n + 1):
              prev = nextArr[i - initialI] = prev * i % m
          self.factorials += nextArr
          return self.factorials[n]
   
      def inv(self, n):
          if n <= -1:
              print("Invalid argument to calculate n^(-1)")
              print("n must be non-negative value. But the argument was " + str(n))
              exit()
          p = self.MOD
          pi = n % p
          if pi < len(self.invModulos):
              return self.invModulos[pi]
          nextArr = [0] * (n + 1 - len(self.invModulos))
          initialI = len(self.invModulos)
          for i in range(initialI, min(p, n + 1)):
              next = -self.invModulos[p % i] * (p // i) % p
              self.invModulos.append(next)
          return self.invModulos[pi]
   
      def invFactorial(self, n):
          if n <= -1:
              print("Invalid argument to calculate (n^(-1))!")
              print("n must be non-negative value. But the argument was " + str(n))
              exit()
          if n < len(self.invFactorial_):
              return self.invFactorial_[n]
          self.inv(n)  # To make sure already calculated n^-1
          nextArr = [0] * (n + 1 - len(self.invFactorial_))
          initialI = len(self.invFactorial_)
          prev = self.invFactorial_[-1]
          p = self.MOD
          for i in range(initialI, n + 1):
              prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
          self.invFactorial_ += nextArr
          return self.invFactorial_[n]
   
   
  class Combination:
      def __init__(self, MOD):
          self.MOD = MOD
          self.factorial = Factorial(MOD)
   
      def ncr(self, n, k):
          if k < 0 or n < k:
              return 0
          k = min(k, n - k)
          f = self.factorial
          return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
  
  class Dsu:
      def __init__(self, n):
          self.parent = list(range(n))
          self.rank = [1] * n
  
      def find(self, x):
          while x != self.parent[x]:
              self.parent[x] = self.parent[self.parent[x]]
              x = self.parent[x]
          return x
  
      def union(self, x, y):
          px, py = self.find(x), self.find(y)
          if px == py: return 0
          if self.rank[py] > self.rank[px]:
              px, py = py, px
          self.parent[py] = px
          self.rank[px] += self.rank[py]
          return 1
  
      def get_size(self, x):
          return self.rank[self.find(x)]
  # endregion ------------------------------------------------------------------------|
  
  c = Combination(mod)
  def solve():
      n, k = ints()
      even = 0; odd = 0
      for i in range(n):
          if i & 1: odd += c.ncr(n, i) % mod
          else: even += c.ncr(n, i) % mod
  
      dp = [[0, 0] for i in range(k + 1)]
      dp[0][0] = 1
      for i in range(1, k + 1):
          dp[i][1] += (dp[i - 1][1] * odd) % mod
          dp[i][1] += (dp[i - 1][1] * even) % mod
          dp[i][0] += (dp[i - 1][0] * even) % mod
          dp[i][1] += (dp[i - 1][1]) % mod
          if n & 1:
              dp[i][0] += (dp[i - 1][0]) % mod
          else:
              dp[i][1] += (dp[i - 1][0]) % mod
      
      print((dp[-1][0] + dp[-1][1]) % mod)
  
  
  
      return
  
  test(int(re()))
  