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.*;
  
  @SuppressWarnings("WeakerAccess")
  public class Main {
  
      private static FastScanner in = new FastScanner();
      private static FastOutputJ out = new FastOutputJ();
  
      private static final long MOD = (long) (1e+9 + 7);
      private static final long[] powsOf2 = new long[(int) (2 * 1e5 + 1)];
  
      private static long mod(long n) {
          return n % MOD;
      }
  
      static {
          powsOf2[0] = 1;
          for (int i = 1; i < powsOf2.length; i++) {
              powsOf2[i] = mod(powsOf2[i - 1] << 1);
          }
      }
  
      private long pow2(int n) {
          return powsOf2[n];
      }
  
      private long mulMod(long a, long b) {
          return mod(a * b);
      }
  
      private long sumMod(long a, long b) {
          return mod(a + b);
      }
  
      public void run() throws Exception {
          int t = in.nextInt();
          for (int i = 0; i < t; i++) {
              int n = in.nextInt();
              int k = in.nextInt();
  
              long prevEq = 1;
              long prevNeq = 0;
  
              long pow2sub1 = sumMod(pow2(n - 1), -1);
              long pow2plus1 = sumMod(pow2(n - 1), 1);
              long pow2ni = 1;
  
              for (int j = 0; j < k; j++) {
                  long curEq, curNeq;
                  if (n % 2 == 0) {
                      curEq = mulMod(prevEq, pow2sub1);
  
                      long eqNowNeqInPrev = mulMod(prevNeq, pow2sub1);
                      long neqNowAnythingInPrev = pow2ni;
                      pow2ni = mulMod(pow2ni, pow2(n));
                      curNeq = sumMod(eqNowNeqInPrev, neqNowAnythingInPrev);
                  } else {
                      curEq = mulMod(prevEq, pow2plus1);
                      curNeq = 0;
                  }
                  prevEq = curEq;
                  prevNeq = curNeq;
              }
              out.println(sumMod(prevEq, prevNeq));
          }
      }
  
      public static void main(String[] args) throws Exception {
          new Main().run();
          out.flush();
          out.close();
      }
  }
  
  
  class FastScanner {
      BufferedReader br;
      StringTokenizer st;
  
      FastScanner() {
          this(System.in);
      }
  
      FastScanner(InputStream stream) {
          br = new BufferedReader(new InputStreamReader(stream));
      }
  
      FastScanner(File file) {
          try {
              br = new BufferedReader(new FileReader(file));
          } catch (FileNotFoundException e) {
              throw new RuntimeException(e);
          }
      }
  
      String next() {
          while (st == null || !st.hasMoreTokens()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  throw new RuntimeException(e);
              }
  
          }
          return st.nextToken();
      }
  
      int nextInt() {
          return Integer.parseInt(next());
      }
  
      int[] nextIntArray(int n) {
          int[] arr = new int[n];
          for (int i = 0; i < n; i++) {
              arr[i] = nextInt();
          }
          return arr;
      }
  
      long[] nextLongArray(int n) {
          long[] arr = new long[n];
          for (int i = 0; i < n; i++) {
              arr[i] = nextLong();
          }
          return arr;
      }
  
      long nextLong() {
          return Long.parseLong(next());
      }
  
      public String nextLine() {
          try {
              return br.readLine();
          } catch (IOException e) {
              throw new RuntimeException(e);
          }
      }
  }
  
  class FastOutputJ {
      private final BufferedWriter bf;
  
  
      public FastOutputJ(OutputStream outputStream) {
          bf = new BufferedWriter(new OutputStreamWriter(outputStream));
      }
  
      public FastOutputJ() {
          this(System.out);
      }
  
      private void printOne(Object s) {
          try {
              bf.write(s.toString());
          } catch (IOException e) {
              throw new RuntimeException(e);
          }
      }
  
      public void println(Object s) {
          printOne(s);
          printOne("\n");
      }
  
      public void print(Object... os) {
          printd("", os);
      }
  
      public void printd(String delimiter, Object... os) {
          for (Object o : os) {
              printOne(o);
              printOne(delimiter);
          }
      }
  
      public void flush() {
          try {
              bf.flush();
          } catch (IOException e) {
              throw new RuntimeException(e);
          }
      }
  
      public void close() {
          try {
              bf.close();
          } catch (IOException e) {
              throw new RuntimeException(e);
          }
      }
  }