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.StringTokenizer;
  
  //https://codeforces.com/contest/1557/problem/C
  //tutorial: https://codeforces.com/blog/entry/93703
  public class CF_1557c{
      static int MOD= 1_000_000_007;
      public static final void main(String[] args){
          Kattio io= new Kattio();
          int t= io.getInt(), maxN= 0;
          int[][] tests= new int[t][2];
          for(int i=0; i<t; i++){
              tests[i][0]= io.getInt();
              tests[i][1]= io.getInt();
              maxN= Math.max(maxN, tests[i][0]);
          }
          MathUtils.setMaxFactorial(maxN);
          for(int[] test:tests){
              int n= test[0], k= test[1];
              // dp[i][0/1] := number of ways a1&a2&..&an >= a1^a2&..&an (0 >, 1==)
              // in the most significant i out of k bits
              long modPow2n= MathUtils.modPow(2, n, MOD);
              long evenCmbLessN= 0;
              for(int i=0; i<n; i+=2){
                  evenCmbLessN+= MathUtils.modCombinations(n, i, MOD);
                  evenCmbLessN%= MOD;
              }
              //if(DEBUG) err("n=%d, k=%d, 2**n=%d, evenCmbLessN=%d", n, k, modPow2n, evenCmbLessN);
              long[][] dp= new long[k+1][2];
              dp[0][0]= 0;
              dp[0][1]= 1;
              for(int i=1; i<=k; i++){
                  // >, n is odd or even
                  // if > in higher bits, anything goes in less significant bits
                  dp[i][0]= (modPow2n*dp[i-1][0]) %MOD;   
                  // ==
                  if((n&1)==1){ // n is odd
                      // either pick even number of 1's out of n or all 1's for game to stay equal
                      dp[i][1]= ( dp[i-1][1] * (evenCmbLessN + 1) ) %MOD;
                  }else{ // n is even
                      // pick even number of 1's (<n) out of n for game to stay equal
                      dp[i][1]= ( dp[i-1][1] * evenCmbLessN ) %MOD;
                      // or pick all 1's for & to become greater than ^
                      dp[i][0]= ( dp[i][0] + dp[i-1][1] ) %MOD;
                  }
              }
              long ways= dp[k][0] + dp[k][1];
              //if(DEBUG) err("dp=%s", ArrayUtils.toString(dp, ", "));
              io.println((int)(ways%MOD));
          }
          io.close();
      }
  
      static class MathUtils {
  
          private static int FACTORIAL_MAX_N = 10;
          private static long[] FACTORIALS= new long[FACTORIAL_MAX_N+1];
      
          public static void setMaxFactorial(int maxN){
              FACTORIAL_MAX_N = maxN;
              FACTORIALS= new long[FACTORIAL_MAX_N+1];
          }
      
          public static long modFactorial(int n, int m){
              if(n>FACTORIAL_MAX_N)
                  throw new RuntimeException(String.format("n=%d is greater than max for factorial(n)", n));
              if(FACTORIALS[n]!=0) return FACTORIALS[n];
              return FACTORIALS[n]= n<2 ? 1L : modMult(n, modFactorial(n-1, m), m);
          }
      
          public static long modCombinations(int n, int k, int m){
              return modDiv(modFactorial(n, m), modMult(modFactorial(n-k, m), modFactorial(k, m), m), m);
          }
      
          public static long modDiv(long a, long b, int m){
              return ((a % m) * modPow(b, m-2, m)) % m;
          }
      
          public static long modMult(long a, long b, int m){
              return ((a % m) * (b % m)) % m;
          }
      
          public static long modPow(long b, long e, int m){
              if(m == 1) return 0;
              long res= 1;
              b= b % m;
              while(e>0){
                  if(e%2 == 1) res= (res*b) % m;
                  e = e >> 1; // e/= 2
                  b = (b*b) % m;
              }
              return res;
          }
      }    
  
      static class Kattio extends PrintWriter {
          private BufferedReader r;
          private String line, token;
          private StringTokenizer st;
      
          public Kattio(){this(System.in);}
          public Kattio(InputStream i){
          super(new BufferedOutputStream(System.out));
              r= new BufferedReader(new InputStreamReader(i));
          }
          public Kattio(InputStream i, OutputStream o){
          super(new BufferedOutputStream(o));
              r= new BufferedReader(new InputStreamReader(i));
          }
          public boolean isLineEnd(){
              return !st.hasMoreTokens();
          }
          public boolean hasMoreTokens(){
              return peekToken()!=null;
          }
          public int getInt(){
              return Integer.parseInt(nextToken());
          }
          public double getDouble(){ 
              return Double.parseDouble(nextToken());
          }
          public long getLong(){
              return Long.parseLong(nextToken());
          }
          public String getWord(){
              return nextToken();
          }
          private String peekToken(){
              if(token==null) try {
                  while(st==null || !st.hasMoreTokens()) {
                      line= r.readLine();
                      if(line==null) return null;
                      st= new StringTokenizer(line);
                  }
                  token= st.nextToken();
              }catch(IOException e){}
              return token;
          }
          private String nextToken() {
              String ans= peekToken();
              token= null;
              return ans;
          }
      }    
  }