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.util.ArrayList;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.PriorityQueue;
  import java.util.StringTokenizer;
  import java.io.*;
   
  public class MoamenXOR {
  	
  	private static class MyScanner {
  	    BufferedReader br;
  	    StringTokenizer st;
   
  	    public MyScanner() {
  	       br = new BufferedReader(new InputStreamReader(System.in));
  	    }
   
  	    String next() {
  	        while (st == null || !st.hasMoreElements()) {
  	            try {
  	                st = new StringTokenizer(br.readLine());
  	            } catch (IOException e) {
  	                e.printStackTrace();
  	            }
  	        }
  	        return st.nextToken();
  	    }
   
  	    int nextInt() {
  	        return Integer.parseInt(next());
  	    }
   
  	    long nextLong() {
  	        return Long.parseLong(next());
  	    }
   
  	    double nextDouble() {
  	        return Double.parseDouble(next());
  	    }
   
  	    String nextLine(){
  	        String str = "";
  		  try {
  		     str = br.readLine();
  		  } catch (IOException e) {
  		     e.printStackTrace();
  		  }
  		  return str;
  	    }
   
  	 }
  	
   
  	public static long exp(long a, long b)
  	{
  		long res = 1;
  		long m = 1000000007;
  		
  		while(b>0)
  		{
  		if(b%2==1)
  			res = (res * a)%m;
  		a = (a * a)%m;	
  		b/=2;
  		}
  		
  		return res;
  	}
  	
  	public static long[] fact;
  	public static HashMap<Long,Long> inv;
  	
  	public static void findfact(long[] arr)
  	{
  		long res = 1;
  		long m = 1000000007;
  		long a = 1;
  		
  		while(a<=200000)
  		  { 
  			res = (res * a)%m;
  		    arr[(int)a-1] = res;
  		    a++;
  		  }
  		
  	}
  	
  	public static long fact(long a)
  	{
  		if(a==0)
  			return 1;
  		return fact[(int)a-1];
  	}
  	
  	public static long choose(long n, long r)
  	{
  		long res = 1;
  		long m = 1000000007;
  		long a = fact(n);
  		long b = fact(n-r);
  		long c = fact(r);
  		long d = (b * c)%m;
  		
  		if(!inv.containsKey(d))
  			inv.put(d,exp(d,m-2));
  		
  		res = (a*(inv.get(d)))%m;
  		
  		return res;
  	}
  	
  	public static long solution(int n, int k)			
  	{
  		if(k==0)
  			return 1;
  		
  		long x = 0;
  		long m = 1000000007;
  		long ans = 0;
  		
  		for(int i = 0; i<=n; i+=2)
  		   x = (x + choose(n,i))%m;
  		
  		if(n%2==0)
  		{
  			x = (x - 1 + m)%m;
  			long y = exp(2,n);
  			
  			for(int i = 0; i< k; i++)
  			   ans = (ans + (exp(x,i) * exp(y,k-1-i))%m)%m; 
  			
  			ans = (ans + exp(x,k))%m;
  			
  		}
  		
  		if(n%2==1)
  			{ x = (x + 1)%m;
  		      ans = exp(x,k); }
  		
  		return ans;
  	
  	}
          
  private static PrintWriter out = new PrintWriter(System.out);
   
  public static void main (String[] args)
  {
  	MyScanner s =  new MyScanner();
      
      int t = s.nextInt();
      fact = new long[200000];
      inv = new HashMap<>();
      
  	findfact(fact);
  	
      for(int j = 0; j<t ; j++)
      {
      	int n = s.nextInt();
      	int k = s.nextInt();
      	out.println(solution(n,k));
      }
   
      
      out.flush();
      out.close();
      
  }
  }