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.PrintWriter;
  import java.util.Arrays;
  import java.util.Scanner;
  //https://codeforces.com/contest/1557/problem/C
  
  /*
  * like this problem, provide another way to see the problem
  * first solve it using dp and then use math way
  * when you see & or ^ operation, you should think about odd or even operation
  * another thing you should consider is for each bit they do not have connection
  *
  * so for this problem, you should consider two cases
  * first is when n is odd
  * you could see when we have even number of 1 could make that happen in all position so it is just pow(ok, k)
  * ok means number of even number of selection in array size of n
  *
  * when n is odd
  * you should consider when we have all the one in a row, interesting part is that and is larger than xor
  * so no matter what you choose in the rest part, you are always larger than xor part
  *
  * which means you only need to calculate the part when xor = and is equal * when xor > and
  *
  * */
  public class MoamenandXOR {
      //    MUST SEE BEFORE SUBMISSION
  //    check whether int part would overflow or not, especially when it is a * b!!!!
  //    check if top down dp would cause overflow or not
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          PrintWriter pw = new PrintWriter(System.out);
          int t = sc.nextInt();
  //        int t = 1;
          comb = new Combinatorial(mod, maxN);
          for (int i = 0; i < t; i++) {
              solve(sc, pw);
          }
          pw.close();
      }
      static int mod = (int) 1e9 + 7;
      static int maxN = (int) 2e5 + 5;
      static Combinatorial comb;
      static long CountNumberOfEvenScenario;
      static void solve(Scanner in, PrintWriter out){
          int n = in.nextInt(), k = in.nextInt();
          long mut = 1;
          for (int i = 0; i < n; i++) {
              mut = (mut * 2) % mod;
          }
          CountNumberOfEvenScenario = 0;
          for (int i = 0; i < n; i += 2) {
              CountNumberOfEvenScenario = (CountNumberOfEvenScenario + comb.ncr(n, i)) % mod;
          }
  //        System.out.println(CountNumberOfEvenScenario);
          long[][] dp = new long[k + 1][2];
          for (int i = 0; i < dp.length; i++) {
              Arrays.fill(dp[i], -1);
          }
          out.println(dfs(k, 0, dp, mut, n));
      }
      static long dfs(int pos, int isEqual, long[][] dp, long Npow2, int n){ // when isEqual is 0 means equal and vice versa
          if (pos < 1) return 1;
  
          if (dp[pos][isEqual] != -1) return dp[pos][isEqual];
          if (isEqual == 1){
              return dp[pos][isEqual] = mut(Npow2, dfs(pos - 1, isEqual, dp, Npow2, n));
          }
          if (n % 2 == 0){
              dp[pos][isEqual] = mut(CountNumberOfEvenScenario, dfs(pos - 1, isEqual, dp, Npow2, n));
              dp[pos][isEqual] = (dp[pos][isEqual] + dfs(pos - 1, 1, dp, Npow2, n)) % mod;
              return dp[pos][isEqual];
          }else{
              return dp[pos][isEqual] = (mut(CountNumberOfEvenScenario + 1, dfs(pos - 1, isEqual, dp, Npow2, n))) % mod;
          }
      }
      static long mut(long a, long b){
          return (a * b) % mod;
      }
  
      // credits to cuiaoxiang
      static class Combinatorial {
  
          int MOD;
          int n;
          long[] fact;
          long[] inv;
          long[] ifact;
          public Combinatorial(int mod, int n) {
              this.MOD = mod;
              this.n = n;
              fact = new long[n + 1];
              inv = new long[n + 1];
              ifact = new long[n + 1];
              inv[1] = 1;
              for (int i = 2; i < n; ++i) {
                  inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
              }
              fact[0] = ifact[0] = 1;
              for (int i = 1; i < n; ++i) {
                  fact[i] = fact[i - 1] * i % MOD;
                  ifact[i] = ifact[i - 1] * inv[i] % MOD;
              }
  
          }
  
          long ncr(int n, int m){
              if (n < m || m < 0) return 0;
              return fact[n] * ifact[m] % MOD * ifact[n - m] % MOD;
          }
      }
  
  
  
  }
  