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.*;
  import java.util.*;
  
  public class Main {
  
      private static final long MOD = 1000000007;
  
      static int[] readArray(int size, InputReader in, boolean subOne) {
          int[] a = new int[size];
          for (int i = 0; i < size; i++) {
              a[i] = in.nextInt() + (subOne ? -1 : 0);
          }
          return a;
      }
  
      static long[] readLongArray(int size, InputReader in) {
          long[] a = new long[size];
          for (int i = 0; i < size; i++) {
              a[i] = in.nextLong();
          }
          return a;
      }
  
      static void sortArray(int[] a) {
          Random random = new Random();
  
          for (int i = 0; i < a.length; i++) {
              int randomPos = random.nextInt(a.length);
              int t = a[i];
              a[i] = a[randomPos];
              a[randomPos] = t;
          }
          Arrays.sort(a);
      }
  
      public static void main(String[] args) throws FileNotFoundException {
  //        InputReader in = new InputReader(new FileInputStream("input.txt"));
  //        PrintWriter out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("milkvisits.out")));
  //
          InputReader in = new InputReader(System.in);
          PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  
          long[] facts = new long[200005];
          long[] invFacts = new long[200005];
          facts[0] = 1;
          invFacts[0] = 1;
          long[] allInvs = allInvs(200005, MOD);
          for (int i = 1; i <= 200004; i++) {
              facts[i] = facts[i - 1] * i % MOD;
              invFacts[i] = invFacts[i - 1] * allInvs[i] % MOD;
          }
  
  
          int t = in.nextInt();
          for (int ii = 0; ii < t; ii++) {
              int n = in.nextInt();
              int k = in.nextInt();
  
              long sumEven = n % 2;
              long sumOdd = 0;
  
              for (int i = 0; i < n; i += 2) {
                  sumEven = (sumEven + facts[n] * invFacts[i] % MOD * invFacts[n - i] % MOD) % MOD;
              }
              for (int i = 1; i < n; i += 2) {
                  sumOdd = (sumOdd + facts[n] * invFacts[i] % MOD * invFacts[n - i] % MOD) % MOD;
              }
  
              long ans = 0;
              long prev = 1;
              for (int i = 0; i < k; i++) {
                  ans = (ans + prev * sumOdd % MOD * fastPow(2, ((long) (k - i - 1)) * n, MOD) % MOD) % MOD;
                  prev = (prev * sumEven) % MOD;
              }
  
              long all = fastPow(2, ((long) k) * n, MOD);
              out.println(subMod(all, ans, MOD));
          }
  
          out.close();
      }
  
      private static long fastPow(long x, long y, long mod) {
          if (x == 1) {
              return 1;
          }
          if (y == 0) {
              return 1;
          }
          long p = fastPow(x, y / 2, mod) % mod;
          p = p * p % mod;
          if (y % 2 == 1) {
              p = p * x % mod;
          }
          return p;
      }
  
      private static long[] allInvs(int n, long mod) {
          long[] inv = new long[n + 1];
          inv[1] = 1;
          for (int i = 2; i <= n; ++i) {
              inv[i] = subMod(mod, (mod / i) * inv[(int) (mod % i)] % mod, mod);
          }
          return inv;
  
      }
  
      private static long subMod(long x, long y, long mod) {
          long res = x - y;
          if (res < 0) {
              return res + mod;
          }
          return res;
      }
  
  
      private static void outputArray(int[] ans, PrintWriter out, boolean addOne) {
          StringBuilder str = new StringBuilder();
          for (int i = 0; i < ans.length; i++) {
              long an = ans[i] + (addOne ? 1 : 0);
              str.append(an).append(' ');
          }
          out.println(str);
      }
  
      private static void outputArray(List<Integer> ans, PrintWriter out, boolean addOne) {
          StringBuilder str = new StringBuilder();
          for (int j = 0; j < ans.size(); j++) {
              long i = ans.get(j);
              long an = i + (addOne ? 1 : 0);
              str.append(an);
              if (j < ans.size() - 1) {
                  str.append(' ');
              }
          }
          out.println(str);
  //        out.flush();
      }
  
      private static class InputReader {
          public BufferedReader reader;
          public StringTokenizer tokenizer;
  
          public InputReader(InputStream stream) {
              reader = new BufferedReader(new InputStreamReader(stream), 32768);
              tokenizer = null;
          }
  
          public String next() {
              while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                  try {
                      tokenizer = new StringTokenizer(reader.readLine());
                  } catch (IOException e) {
                      throw new RuntimeException(e);
                  }
              }
              return tokenizer.nextToken();
          }
  
          public String nextString() {
              try {
                  return reader.readLine();
              } catch (IOException e) {
                  throw new RuntimeException(e);
              }
          }
  
          public int nextInt() {
              return Integer.parseInt(next());
          }
  
          public long nextLong() {
              return Long.parseLong(next());
          }
  
          public double nextDouble() {
              return Double.parseDouble(next());
          }
  
          public char nextChar() {
              return next().charAt(0);
          }
  
          public String nextWord() {
              return next();
          }
  
          private List<Integer>[] readTree(int n) {
              return readGraph(n, n - 1);
          }
  
          private List<Integer>[] readGraph(int n, int m) {
              List<Integer>[] result = new ArrayList[n];
              for (int i = 0; i < n; i++) {
                  result[i] = new ArrayList<>();
              }
              for (int i = 0; i < m; i++) {
                  int u = nextInt() - 1;
                  int v = nextInt() - 1;
                  result[u].add(v);
                  result[v].add(u);
              }
              return result;
          }
  
          private Map<Integer, Long>[] readWeightedGraph(int n, int m) {
              Map<Integer, Long>[] result = new HashMap[n];
              for (int i = 0; i < n; i++) {
                  result[i] = new HashMap<>();
              }
              for (int i = 0; i < m; i++) {
                  int u = nextInt() - 1;
                  int v = nextInt() - 1;
                  long w = nextLong();
                  result[u].put(v, Math.min(w, result[u].getOrDefault(v, Long.MAX_VALUE)));
                  result[v].put(u, Math.min(w, result[v].getOrDefault(u, Long.MAX_VALUE)));
              }
              return result;
          }
  
      }
  }