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.*;
   public class Ccoder
   {
       static long pow(long a , long b , long c)
  {
      if(b == 0)
      return 1;
      
      long ans = pow(a,b/2,c);
      if(b%2 == 0)
      return ans*ans%c;
      
      return ans*ans%c*a%c;
  }
       public static void main(String []args)
      {
          Scanner sc = new Scanner(System.in);
          int t = sc.nextInt();
          long mod = 1000000007;
          long lim = 200000;
          long fact[] = new long[(int)(lim+1)];
          long inv[] = new long[(int)(lim+1)];
          fact[0] = 1;
          inv[0] = 1;
          for(long i = 1 ; i <= lim ; i++)
          {
              fact[(int)i] = fact[(int)(i-1)]*i%mod;
              inv[(int)i] = pow(fact[(int)i],mod-2,mod);
          }
          
          
          while(t-- > 0)
          {
              int n = sc.nextInt();
              int k = sc.nextInt();
              
              if(k == 0)
              System.out.println(1);
              
              else
              {
              if(n%2 == 0)
              {
                  long pr = 1;
                  long ans = 0;
                  long pre = 0;
                  for(int i = 2 ; i <= n ; i+= 2)
                  {
                      pre += (fact[n]*inv[i]%mod*inv[n-i]%mod);
                      pre %= mod;
                  }
                  //System.out.println(pre + " boob");
                  
                  for(int i = 0 ; i < k ; i++)
                  {
                      long x = (long)(k-i-1)*(long)n;
                     ans += pr*pow(2,x,mod);
                     //System.out.println(pr + " " + pow(2,x,mod));
                     ans %= mod;
                     pr = pr*pre;
                     pr %= mod;
                     
                     
                  }
                  
                  //System.out.println(pr);
                  ans += pr;
                  ans %= mod;
                  System.out.println(ans);
              }
              
              else
              {
                  long ans = 1;
                  for(int i = 1 ; i <= n ; i += 2)
                  {
                      ans += fact[n]*inv[i]%mod*inv[n-i]%mod;
                      ans %= mod;
                  }
                  System.out.println(pow(ans,k,mod));
              }
              
             
              }
          }
      }
  }