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 static java.lang.Math.max;
  import static java.lang.Math.min;
  import static java.lang.Math.abs;
  import java.util.*;
  import java.io.*;
  
  public class A
  {
      static int n, k;
      static int[] arr;
      static char[] s;
      public static void main(String[] args) throws IOException
      {
          f = new Flash();
          out = new PrintWriter(System.out);
          compute();
          int T = ni();
          for(int tc = 1; tc <= T; tc++){
          	n = ni(); k = ni(); sop(fn());
          }
          
          out.flush(); out.close();
      }
      
      static long fn()
      {
      	if(n%2 == 1) {
      		long x = 0;
          	for(int i = 0; i <= n; i += 2) {
          		x += ncr(n, i);
          		if(x >= mod) x -= mod;
          	}
          	
              long[][] dp = new long[k+1][2];
              dp[0][0] = 1;
              for(int i = 1; i <= k; i++) {
              	dp[i][0] = x*dp[i-1][0];
              	dp[i][0] %= mod;
              	dp[i][0] += x*dp[i-1][1];
              	dp[i][0] %= mod;
              	
              	dp[i][1] = 1*dp[i-1][0];
              	dp[i][1] %= mod;
              	dp[i][1] += 1*dp[i-1][1];
              	dp[i][1] %= mod;
              }
              
              return (dp[k][0]+dp[k][1])%mod;
      	}
      	
      	
      	else {
      		long ans = 0, x = 0;
          	for(int i = 0; i < n; i += 2) {
          		x += ncr(n, i);
          		if(x >= mod) x -= mod;
          	}
          	
      		for(int i = 1; i <= k; i++) {
      			ans += (pow(x, i-1) * pow(2, n*1L*(k-i)))%mod;
      			if(ans >= mod) ans -= mod;
      		}
      		
      		ans += pow(x, k);
      		if(ans >= mod) ans -= mod;
      		return ans;
      	}
      }
      
      static long pow(long x, long p){
          long ans = 1;
      	while(p > 0) {
      		if((p&1) == 1) ans = (ans*x) % mod;
      		x = (x*x) % mod;
      		p >>= 1;
      	}
      	
      	return ans;
      }
       
      static long mod_inv(long x){
          return pow(x, mod-2);
      }
       
      static void compute()
      {
          fact = new long[maxN+1]; fact[0] = 1;
          inv = new long[maxN+1]; inv[0] = 1;
          
          for(int i = 1; i < maxN; i++)
              fact[i] = fact[i-1] * i % mod;
              
          inv[maxN - 1] = mod_inv(fact[maxN - 1]);
          
          for (int i = maxN-2; i > 0; i--)
              inv[i] = inv[i+1] * (i+1) % mod;
      }
       
      static long ncr(int n, int r){
          if (n < 0 || r < 0 || n - r < 0) return 0;
          return fact[n] * inv[r] % mod * inv[n-r] % mod;
      }
      
      static Flash f;
      static PrintWriter out;
      static final long mod = (long)1e9+7;
      static final long inf = (long)1e18;
      static final int _inf = (int)1e9;
      static final int maxN = (int)1e6;
      static long[] fact, inv;
      
      static class cpr implements Comparator<int[]>{
      	public int compare(int[] a, int[] b) {
      		return Integer.compare(a[0], b[0]);
      	}
      }
      
      static void sort(int[] a){
          List<Integer> A = new ArrayList<>();
          for(int i : a) A.add(i);
          Collections.sort(A);
          for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
      }
      
      static void sort(long[] a){
          List<Long> A = new ArrayList<>();
          for(long i : a) A.add(i);
          Collections.sort(A);
          for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
      }
      
      static void print(int[] a){
          StringBuilder sb = new StringBuilder();
          for(int v : a) sb.append(v + " ");
          out.println(sb);
      }
      
      static void print(long[] a){
          StringBuilder sb = new StringBuilder();
          for(long v : a) sb.append(v + " ");
          out.println(sb);
      }
      
      static void print(List<Integer> A){
          StringBuilder sb = new StringBuilder();
          for(int v : A) sb.append(v + " ");
          out.println(sb);
      }
      
      static int swap(int itself, int dummy){return itself;}
      static long swap(long itself, long dummy){return itself;}
      static char swap(char itself, char dummy){return itself;}
      static void sop(Object o){out.println(o);}
      static int ni(){return f.ni();}
      static long nl(){return f.nl();}
      static double nd(){return f.nd();}
      static String next(){return f.next();}
      static String ns(){return f.ns();}
      static String yes = "YES", no = "NO";
      static char[] nc(){return f.nc();}
      static int[] arr(int len){return f.arr(len);}
      static int gcd(int a, int b){if(b == 0) return a; return gcd(b, a%b);}
      static long gcd(long a, long b){if(b == 0) return a; return gcd(b, a%b);}
      static int fcm(int a, int b){return (a*b)/gcd(a, b);}
      static long fcm(long a, long b){return (a*b)/gcd(a, b);}
      static double log2(long N) {return Math.log(N) / Math.log(2);}
      static void debug(int[] a) {sop(Arrays.toString(a));}
      static void debug(long[] a) {sop(Arrays.toString(a));}
      
      static class Flash
      {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer("");
          
          String next(){
              while(!st.hasMoreTokens()){
                  try{
                      st = new StringTokenizer(br.readLine());
                  }catch(IOException e){
                      e.printStackTrace();
                  }
              }
              
              return st.nextToken();
          }
          
          String ns(){
              String s = new String();
              try{
                  s = br.readLine().trim();
              }catch(IOException e){
                  e.printStackTrace();
              }
              
              return s;
          }
          
          int[] arr(int n){
              int[] a = new int[n];
              for(int i = 0; i < n; i++) a[i] = ni();
              return a;
          }
          
          char[] nc(){return ns().toCharArray();}
          int ni(){return Integer.parseInt(next());}
          long nl(){return Long.parseLong(next());}
          double nd(){return Double.parseDouble(next());}
      }
  }