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.FileNotFoundException;
  import java.io.FileReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.io.PrintWriter;
  import java.util.StringTokenizer;
  
  public class Solve6 {
  
      public static void main(String[] args) throws IOException {
          PrintWriter pw = new PrintWriter(System.out);
          new Solve6().solve(pw);
          pw.flush();
          pw.close();
      }
  
      public void solve(PrintWriter pw) throws IOException {
          FastReader sc = new FastReader();
          final int MOD = (int) 1E+9 + 7;
          final int MAX = (int) 2E+5;
          fact = new long[MAX + 1];
          fact[0] = 1;
          for (int i = 1; i <= MAX; i++) {
              fact[i] = (fact[i - 1] * i) % MOD;
          }
          int t = sc.nextInt();
          while (t-- > 0) {
              int n = sc.nextInt(), k = sc.nextInt();
              if (k == 0) {
                  pw.println(1);
                  continue;
              }
              long[] s = combinations(n, MOD);
              long ans = 0;
              for (int i = 0; i <= k; i++) {
                  if ((n & 1) == 0) {
                      ans += pow(s[0], k - i, MOD) * (pow(s[2], Math.max(0, i - 1), MOD));
                  } else {
                      ans += pow(s[0], k - i, MOD) * (pow(s[1], Math.max(0, i - 1), MOD));
                  }
                  ans %= MOD;
              }
              pw.println(ans);
          }
      }
  
      public long pow(long a, long n, int MOD) {
          if (n == 0) {
              return 1;
          }
          long y = pow(a, n >> 1, MOD);
          if ((n & 1) == 0) {
              return (y * y) % MOD;
          }
          return (a * ((y * y) % MOD)) % MOD;
      }
      long[] fact;
  
      public long[] combinations(int n, int MOD) {
          long[] s = new long[3];
          s[0] = 1;
          for (int i = 1; i < n; i++) {
              long ncr = ncr(n, i, MOD);
              if ((i & 1) == 1) {
                  s[2] = (s[2] + ncr) % MOD;
              } else {
                  s[0] = (s[0] + ncr) % MOD;
              }
          }
          s[2] = (s[2] + s[0] + 1) % MOD;
          s[1] = (s[0] + 1) % MOD;
          return s;
      }
  
      public long ncr(int n, int r, int MOD) {
          long denominator = (fact[n - r] * fact[r]) % MOD;
          long multiplicativeInverse = (extendedEuclidean(denominator, MOD)[1] + MOD) % MOD;
          long ans = (fact[n] * multiplicativeInverse) % MOD;
          return ans;
      }
  
      public long[] extendedEuclidean(long a, long b) {
          if (b == 0) {
              return new long[]{a, 1, 0};
          }
          long[] p = extendedEuclidean(b, a % b);
          long d = p[0], x1 = p[1], y1 = p[2];
          long x = y1, y = x1 - (a / b) * y1;
          return new long[]{d, x, y};
      }
  
      static class FastReader {
  
          BufferedReader br;
          StringTokenizer st;
  
          public FastReader() {
              br = new BufferedReader(new InputStreamReader(System.in));
          }
  
          public FastReader(String s) {
              try {
                  br = new BufferedReader(new FileReader(s));
              } catch (FileNotFoundException e) {
              }
          }
  
          public String next() {
              if (st == null || !st.hasMoreTokens()) {
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (Exception e) {
                  }
              }
              return st.nextToken();
          }
  
          public int nextInt() {
              return Integer.parseInt(next());
          }
  
          public long nextLong() {
              return Long.parseLong(next());
          }
  
          public double nextDouble() {
              return Double.parseDouble(next());
          }
  
          public String nextLine() {
              try {
                  return br.readLine();
              } catch (Exception e) {
              }
              return null;
          }
  
          public boolean hasNext() throws IOException {
              if (st != null && st.hasMoreTokens()) {
                  return true;
              }
              String s = br.readLine();
              if (s == null || s.isEmpty()) {
                  return false;
              }
              st = new StringTokenizer(s);
              return true;
          }
      }
  }
  