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.*;
  import java.io.*;
  
  public class Solution
  {
      static class Reader {
          final private int BUFFER_SIZE = 1 << 16;
          private DataInputStream din;
          private byte[] buffer;
          private int bufferPointer, bytesRead;
   
          public Reader()
          {
              din = new DataInputStream(System.in);
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
   
          public Reader(String file_name) throws IOException
          {
              din = new DataInputStream(
                  new FileInputStream(file_name));
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
   
          public String readLine() throws IOException
          {
              byte[] buf = new byte[64]; // line length
              int cnt = 0, c;
              while ((c = read()) != -1) {
                  if (c == '\n') {
                      if (cnt != 0) {
                          break;
                      }
                      else {
                          continue;
                      }
                  }
                  buf[cnt++] = (byte)c;
              }
              return new String(buf, 0, cnt);
          }
   
          public int nextInt() throws IOException
          {
              int ret = 0;
              byte c = read();
              while (c <= ' ') {
                  c = read();
              }
              boolean neg = (c == '-');
              if (neg)
                  c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
   
              if (neg)
                  return -ret;
              return ret;
          }
   
          public long nextLong() throws IOException
          {
              long ret = 0;
              byte c = read();
              while (c <= ' ')
                  c = read();
              boolean neg = (c == '-');
              if (neg)
                  c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (neg)
                  return -ret;
              return ret;
          }
   
          public double nextDouble() throws IOException
          {
              double ret = 0, div = 1;
              byte c = read();
              while (c <= ' ')
                  c = read();
              boolean neg = (c == '-');
              if (neg)
                  c = read();
   
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
   
              if (c == '.') {
                  while ((c = read()) >= '0' && c <= '9') {
                      ret += (c - '0') / (div *= 10);
                  }
              }
   
              if (neg)
                  return -ret;
              return ret;
          }
   
          private void fillBuffer() throws IOException
          {
              bytesRead = din.read(buffer, bufferPointer = 0,
                                   BUFFER_SIZE);
              if (bytesRead == -1)
                  buffer[0] = -1;
          }
   
          private byte read() throws IOException
          {
              if (bufferPointer == bytesRead)
                  fillBuffer();
              return buffer[bufferPointer++];
          }
   
          public void close() throws IOException
          {
              if (din == null)
                  return;
              din.close();
          }
      }
      
     
    static int parent(int a , int p[])
    {
        if(a == p[a])
        return a;
        
        return p[a] = parent(p[a],p);
    }
    
    static void union(int a , int b , int p[] , int size[])
    {
        a = parent(a,p);
        b = parent(b,p);
        
        if(a == b)
        return;
        
        if(size[a] < size[b])
        {
            int temp = a;
            a = b;
            b = temp;
        }
        
        p[b] = a;
        size[a] += size[b];
    }
    
    
    
    
   static long getSum(int index , long BITree[])
      {
          long sum = 0; // Iniialize result
        
          // index in BITree[] is 1 more than
          // the index in arr[]
         // index = index + 1;
        
          // Traverse ancestors of BITree[index]
          while(index>0)
          {
              // Add current element of BITree 
              // to sum
              sum += BITree[index];
        
              // Move index to parent node in 
              // getSum View
              index -= index & (-index);
          }
          return sum;
      }
    
      // Updates a node in Binary Index Tree (BITree)
      // at given index in BITree. The given value 
      // 'val' is added to BITree[i] and all of 
      // its ancestors in tree.
      public static void updateBIT(int n, int index, 
                                          long val , long BITree[])
      {
          // index in BITree[] is 1 more than 
          // the index in arr[]
        //  index = index + 1;
        
          // Traverse all ancestors and add 'val'
          while(index <= n)
          {
          // Add 'val' to current node of BIT Tree
          BITree[index] += val;
        
          // Update index to that of parent 
          // in update View
          index += index & (-index);
          }
      }
      
      
     static int gcd(int a, int b)
  {
      if (a == 0)
          return b;
      return gcd(b % a, a);
  }
  
  static int dp[][];
  
  
  static int f(int pos , int take , int arr[])
  {
      if(pos == -1)
      {
          if(take == 0)
      return 0;
      
      return -10000000;
      
      }
      
      
      if(dp[pos][take] != -1)
      return dp[pos][take];
      
      
      if(pos+1-take == arr[pos])
      dp[pos][take] = Math.max(dp[pos][take],1 + f(pos-1,take,arr));
      
      
      dp[pos][take] = Math.max(dp[pos][take],f(pos-1,take,arr));
      
      
      if(take > 0)
      dp[pos][take] = Math.max(dp[pos][take],f(pos-1,take-1,arr));
      
      return dp[pos][take];
  }
  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) throws IOException
      {
          Reader sc = new Reader();
          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));
              }
              
             
              }
          }
      }
  }