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 java.io.BufferedReader;
  import java.io.BufferedWriter;
  import java.io.File;
  import java.io.FileReader;
  import java.io.FileWriter;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.io.OutputStreamWriter;
  import java.io.PrintWriter;
  import java.lang.reflect.Array;
  import java.util.ArrayDeque;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.Deque;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.LinkedHashMap;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  import java.util.PriorityQueue;
  import java.util.Queue;
  import java.util.Random;
  import java.util.Set;
  import java.util.Stack;
  import java.util.StringTokenizer;
  import java.util.TreeSet;
  import java.util.stream.Collectors;
  
  public class Main {
      static int mod = (int) (1e9) + 7;
  
      /* ======================DSU===================== */
      static class dsu {
          static int parent[], n;// min[],value[];
          static long size[];
  
          dsu(int n) {
              parent = new int[n + 1];
              size = new long[n + 1];
              // min=new int[n+1];
              // value=new int[n+1];
              Main.dsu.n = n;
              makeSet();
          }
  
          static void makeSet() {
              for (int i = 1; i <= n; i++) {
                  parent[i] = i;
                  size[i] = 1;
                  // min[i]=i;
              }
          }
  
          static int find(int a) {
              if (parent[a] == a)
                  return a;
              else {
                  return parent[a] = find(parent[a]);// Path Compression
              }
          }
  
          static void union(int a, int b) {
              int setA = find(a);
              int setB = find(b);
              if (setA == setB)
                  return;
              if (size[setA] >= size[setB]) {
                  parent[setB] = setA;
                  size[setA] += size[setB];
              } else {
                  parent[setA] = setB;
                  size[setB] += size[setA];
              }
          }
      }
  
      /* ======================================================== */
      static class Pair<X extends Number, Y extends Number> implements Comparator<Pair> {
          X x;
          Y y;
  
          // Constructor
          public Pair(X x, Y y) {
              this.x = x;
              this.y = y;
          }
  
          public Pair() {
  
          }
  
          @Override
          public int compare(Main.Pair o1, Main.Pair o2) {
              return ((int) (o1.y.intValue() - o2.y.intValue()));// Ascending Order based on 'y'
          }
      }
  
      /* ===============================Tries================================= */
      static class TrieNode {
          private HashMap<Character, TrieNode> children = new HashMap<>();
          public int size;
          boolean endOfWord;
  
          public void putChildIfAbsent(char ch) {
              children.putIfAbsent(ch, new TrieNode());
          }
  
          public TrieNode getChild(char ch) {
              return children.get(ch);
          }
      }
  
      static private TrieNode root;
  
      public static void insert(String str) {
          TrieNode curr = root;
          for (char ch : str.toCharArray()) {
              curr.putChildIfAbsent(ch);
              curr = curr.getChild(ch);
              curr.size++;
          }
          // mark the current nodes endOfWord as true
          curr.endOfWord = true;
      }
  
      public static int search(String word) {
          TrieNode curr = root;
  
          for (char ch : word.toCharArray()) {
              curr = curr.getChild(ch);
              if (curr == null) {
                  return 0;
              }
          }
          // size contains words starting with prefix- word
          return curr.size;
      }
  
      public boolean delete(TrieNode current, String word, int index) {
          if (index == word.length()) {
              // when end of word is reached only delete if currrent.endOfWord is true.
              if (!current.endOfWord) {
                  return false;
              }
              current.endOfWord = false;
              // if current has no other mapping then return true
              return current.children.size() == 0;
          }
          char ch = word.charAt(index);
          TrieNode node = current.children.get(ch);
          if (node == null) {
              return false;
          }
          boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
  
          // if true is returned then delete the mapping of character and trienode
          // reference from map.
          if (shouldDeleteCurrentNode) {
              current.children.remove(ch);
              // return true if no mappings are left in the map.
              return current.children.size() == 0;
          }
          return false;
      }
  
      /* ================================================================= */
      static class FastReader {
          BufferedReader br;
          StringTokenizer st;
  
          public FastReader() {
              br = new BufferedReader(new InputStreamReader(System.in));
          }
  
          String next() {
              while (st == null || !st.hasMoreElements()) {
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
  
          int nextInt() {
              return Integer.parseInt(next());
          }
  
          long nextLong() {
              return Long.parseLong(next());
          }
  
          double nextDouble() {
              return Double.parseDouble(next());
          }
  
          String nextLine() {
              String str = "";
              try {
                  str = br.readLine();
              } catch (IOException e) {
                  e.printStackTrace();
              }
              return str;
          }
  
          int[] intArr(int n) {
              int res[] = new int[n];
              for (int i = 0; i < n; i++)
                  res[i] = nextInt();
              return res;
          }
  
          long[] longArr(int n) {
              long res[] = new long[n];
              for (int i = 0; i < n; i++)
                  res[i] = nextLong();
              return res;
          }
      }
  
      static FastReader f = new FastReader();
      static BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
  
      static boolean isPrime(long n) {
          if (n <= 1)
              return false;
          if (n <= 3)
              return true;
          if (n % 2 == 0 || n % 3 == 0)
              return false;
          for (long i = 5; i * i <= n; i = i + 6)
              if (n % i == 0 || n % (i + 2) == 0)
                  return false;
          return true;
      }
  
      static int lowerBound(int a[], int x) { // x is the target, returns lowerBound. If not found return -1
          int l = -1, r = a.length, flag = 0;
          while (l + 1 < r) {
              int m = (l + r) >>> 1;
              if (x == a[m])
                  flag = 1;
              if (a[m] >= x)
                  r = m;
              else
                  l = m;
          }
          return r;
      }
  
      static int upperBound(int a[], int x, int l, int r) {// x is the target, returns upperBound. If not found return -1
          int flag = 0;
          while (l + 1 < r) {
              int m = (l + r) >>> 1;
              if (a[m] == x)
                  return m;
              if (a[m] <= x) {
                  l = m;
                  flag = 1;
              } else
                  r = m;
          }
          return l + 1;
      }
  
      static long gcd(long a, long b) {
          if (a == 0)
              return b;
          return gcd(b % a, a);
      }
  
      static long lcm(long a, long b) {
          return (a * b) / gcd(a, b);
      }
  
      static long power(long x, long y) {
          long res = 1;
          while (y > 0) {
              if (y % 2 == 1)
                  res = (res * x);
              y >>= 1;
              x = (x * x);
          }
          return res;
      }
  
      public double binPow(double x, int n) {// binary exponentiation with negative power as well
          if (n == 0)
              return 1.0;
          double binPow = binPow(x, n / 2);
          if (n % 2 == 0) {
              return binPow * binPow;
          } else {
              return n > 0 ? (binPow * binPow * x) : (binPow * binPow / x);
          }
      }
  
      static long ceil(long x, long y) {
          return (x % y == 0 ? x / y : (x / y + 1));
      }
  
      /*
       * ===========Modular Operations==================
       */
      static long modPower(long x, long y, long p) {
          long res = 1;
          x = x % p;
          while (y > 0) {
              if (y % 2 == 1)
                  res = (res * x) % p;
              y = y >> 1; // y = y/2
              x = (x * x) % p;
          }
          return res;
      }
  
      static long modInverse(long n, long p) {
          return modPower(n, p - 2, p);
      }
  
      static long modAdd(long a, long b) {
          return ((a + b + mod) % mod);
      }
  
      static long modMul(long a, long b) {
          return ((a % mod) * (b % mod)) % mod;
      }
  
      static long[] fac = new long[200000 + 5];
      static long[] invFac = new long[200000 + 5];
  
      static long nCrModPFermat(int n, int r) {
          if (r == 0)
              return 1;
          // return (fac[n] * modInverse(fac[r], mod) % mod * modInverse(fac[n - r], mod)
          // % mod) % mod;
          return (fac[n] * invFac[r] % mod * invFac[n - r] % mod) % mod;
      }
  
      /*
       * ===============================================
       */
  
      static void ruffleSort(long[] a) {
          int n = a.length;
          Random r = new Random();
          for (int i = 0; i < a.length; i++) {
              int oi = r.nextInt(n);
              long temp = a[i];
              a[i] = a[oi];
              a[oi] = temp;
          }
          Arrays.sort(a);
      }
  
      static void ruffleSort(int[] a) {
          int n = a.length;
          Random r = new Random();
          for (int i = 0; i < a.length; i++) {
              int oi = r.nextInt(n);
              int temp = a[i];
              a[i] = a[oi];
              a[oi] = temp;
          }
          Arrays.sort(a);
      }
  
      static String binString32(int n) {
          StringBuilder str = new StringBuilder("");
          String bin = Integer.toBinaryString(n);
          if (bin.length() != 32) {
              for (int k = 0; k < 32 - bin.length(); k++) {
                  str.append("0");
              }
              str.append(bin);
          }
          return str.toString();
      }
  
      static class sparseTable {
          public static int st[][];
          public static int log = 4;
  
          static int func(int a, int b) {// make func as per question(here min range query)
              return (int) gcd(a, b);
          }
  
          void makeTable(int n, int a[]) {
  
              st = new int[n][log];
              for (int i = 0; i < n; i++) {
                  st[i][0] = a[i];
              }
              for (int j = 1; j < log; j++) {
                  for (int i = 0; i + (1 << j) <= n; i++) {
                      st[i][j] = func(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
                  }
              }
          }
  
          static int query(int l, int r) {
              int length = r - l + 1;
              int k = 0;
              while ((1 << (k + 1)) <= length) {
                  k++;
              }
              return func(st[l][k], st[r - (1 << k) + 1][k]);
          }
  
          static void printTable(int n) {
              for (int j = 0; j < log; j++) {
                  for (int i = 0; i < n; i++) {
                      System.out.print(st[i][j] + " ");
                  }
                  System.out.println();
              }
          }
      }
  
      /*
       * ====================================Main=================================
       */
  
      // static int st[], a[];
  
      // static void buildTree(int treeIndex, int lo, int hi) {
      // if (hi == lo) {
      // st[treeIndex] = a[lo];
      // return;
      // }
      // int mid = (lo + hi) / 2;
      // buildTree(treeIndex * 2 + 1, lo, mid);
      // buildTree(treeIndex * 2 + 2, mid + 1, hi);
      // st[treeIndex] = merge(st[treeIndex * 2 + 1], st[treeIndex * 2 + 2]);
      // }
  
      // static void update(int treeIndex, int lo, int hi, int arrIndex, int val) {
      // if (hi == lo) {
      // st[treeIndex] = val;
      // a[arrIndex] = val;
      // return;
      // }
      // int mid = (hi + lo) / 2;
      // if (mid < arrIndex) {
      // update(treeIndex * 2 + 2, mid + 1, hi, arrIndex, val);
      // } else {
      // update(treeIndex * 2 + 1, lo, mid, arrIndex, val);
      // }
      // st[treeIndex] = merge(st[treeIndex * 2 + 1], st[treeIndex * 2 + 2]);
      // }
  
      // static int query(int treeIndex, int lo, int hi, int l, int r) {
      // if (l <= lo && r >= hi) {
      // return st[treeIndex];
      // }
      // if (l > hi || r < lo) {
      // return 0;
      // }
      // int mid = (hi + lo) / 2;
      // return query(treeIndex * 2 + 1, lo, mid, l, Math.min(mid, r));
      // }
  
      // static int merge(int a, int b) {
      // return a + b;
      // }
  
      public static long findKthPositive(long[] A, long k) {
          int l = 0, r = A.length, m;
          while (l < r) {
              m = (l + r) / 2;
              if (A[m] - 1 - m < k)
                  l = m + 1;
              else
                  r = m;
          }
          return l + k;
      }
  
      static int[] z_function(char ar[]) {
          int[] z = new int[ar.length];
          z[0] = ar.length;
          int l = 0;
          int r = 0;
          for (int i = 1; i < ar.length; i++) {
              if (r < i) {
                  l = i;
                  r = i;
                  while (r < ar.length && ar[r - l] == ar[r])
                      r++;
                  z[i] = r - l;
                  r--;
              } else {
                  int k = i - l;
                  if (z[k] < r - i + 1) {
                      z[i] = z[k];
                  } else {
                      l = i;
                      while (r < ar.length && ar[r - l] == ar[r])
                          r++;
                      z[i] = r - l;
                      r--;
                  }
              }
          }
          return z;
      }
  
      // BINARY SEARCH
      // count of set bits in a particular position
      // suffix max array/ suffix sum array/ prefix
      static long min, dp[][];
      static ArrayList<Integer> mask;
      static long ans;
  
      public static void main(String args[]) throws Exception {
          int t = 1;
          t = f.nextInt();
          int tc = 1;
          fac[0] = 1;
          for (int i = 1; i <= 200000; i++) {
              fac[i] = fac[i - 1] * i % mod;
              invFac[i] = modInverse(fac[i], mod);
          }
  
          while (t-- != 0) {
              int n = f.nextInt();
              int k = f.nextInt();
              long ans = 0;
              if (k == 0) {
                  ans = 1;
              } else {
                  if (n % 2 == 0) {
                      // AND>=XOR
                      long a1 = 0;
                      for (int i = 0; i < n; i += 2) {
                          a1 = modAdd(a1, nCrModPFermat(n, i));// even number of ones at a certain bit position
                      }
                      long exp = modPower(a1, k, mod);// permutations for all bit positions
                      for (int i = 0; i < k; i++) {
                          long left = modPower(a1, i, mod);// choices for the left side when standing at i
                          long right = modPower(modPower(2, n, mod), k - 1 - i, mod);// choices for the right side when
                                                                                     // standing at i
                          exp = modAdd(exp, modMul(left, right));// total choices = left*right;
                      }
                      ans = exp;
                  } else {
                      // AND==XOR==0
                      long a2 = 1;// all ones
                      for (int i = 0; i < n; i += 2) {
                          a2 = modAdd(a2, nCrModPFermat(n, i));//even number of ones at a certain bit position but not all ones
                      }
                      long exp = modPower(a2, k, mod);
                      ans = exp;
                  }
              }
              w.write(ans + "\n");
          }
          w.flush();
      }
  }
  /*
   */