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.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.io.PrintWriter;
  import java.util.Arrays;
  import java.util.HashMap;
  import java.util.InputMismatchException;
  import java.util.Map;
  import java.util.TreeSet;
  
  public class Template {
  
    static class Solver implements Runnable {
  
      final int MOD = (int) 1e9 + 7;
      final int _LESSER = 0;
      final int _EQUAL = 1;
      final int _GREATER = 2;
      long xor_0, xor_1;
      long and_0, and_1;
      int n, k;
      long _2pwn, evenAns;
      //    long[][][][] dp;
      long[][] dp;
      InputReader in;
      PrintWriter out;
  
      void solve() throws IOException {
        int t = in.nextInt();
  
        pre();
  
        while (t-- > 0) {
          n = in.nextInt();
          k = in.nextInt();
          dp = new long[k][3];
          _2pwn = CMath.modPower(2, n, MOD);
          evenAns = 0;
  
          for (int i = 0; i < n; i += 2) {
            evenAns = CMath.mod(evenAns + nCR(n, i), MOD);
          }
  
          for (int i = 0; i < k; i++) {
            Arrays.fill(dp[i], -1);
          }
  
          out.println(find(0, _EQUAL));
        }
      }
  
      long find(int ind, int eq) {
        if (ind == k) {
          return 1;
        }
  
        if (dp[ind][eq] != -1) {
          return dp[ind][eq];
        }
  
        if (eq == _GREATER) {
          return dp[ind][eq] = CMath.mod(_2pwn * find(ind + 1, _GREATER), MOD);
        }
  
        if (n % 2 == 1) {
          return dp[ind][eq] = CMath.mod((evenAns + 1) * find(ind + 1, _EQUAL), MOD);
        }
  
        return dp[ind][eq] = CMath.modAdd(
            MOD,
            CMath.mod(evenAns * find(ind + 1, _EQUAL), MOD),
            CMath.mod(find(ind + 1, _GREATER), MOD)
        );
      }
  
      long[] fact, invFact;
  
      void pre() {
        fact = new long[(int) 1e6 + 5];
        invFact = new long[(int) 1e6 + 5];
        fact[0] = 1;
  
        for (int i = 1; i <= 1e6; i++) {
          fact[i] = CMath.mod(fact[i - 1] * i, MOD);
        }
  
        invFact[(int) 1e6] = CMath.moduloInverse(fact[(int) 1e6], MOD);
  
        for (int i = (int) 1e6; i > 0; i--) {
          invFact[i - 1] = CMath.mod(invFact[i] * i, MOD);
        }
      }
  
      long nCR(int n, int r) {
        return CMath.mod(CMath.mod(fact[n] * invFact[r], MOD) * invFact[n - r], MOD);
      }
  
      public Solver(InputReader in, PrintWriter out) {
        this.in = in;
        this.out = out;
      }
  
      @Override
      public void run() {
        try {
          solve();
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
  
    }
  
    static class InputReader {
  
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
  
      public int read() {
        if (numChars == -1) {
          throw new InputMismatchException();
        }
  
        if (curChar >= numChars) {
          curChar = 0;
          try {
            numChars = stream.read(buf);
          } catch (IOException e) {
            throw new InputMismatchException();
          }
          if (numChars <= 0) {
            return -1;
          }
        }
  
        return buf[curChar++];
      }
  
      public int nextInt() {
        int c = read();
  
        while (isSpaceChar(c)) {
          c = read();
        }
  
        int sgn = 1;
  
        if (c == '-') {
          sgn = -1;
          c = read();
        }
  
        int res = 0;
  
        do {
          if (c < '0' || c > '9') {
            throw new InputMismatchException();
          }
  
          res *= 10;
          res += c & 15;
  
          c = read();
        } while (!isSpaceChar(c));
  
        return res * sgn;
      }
  
      public int[] nextIntArray(int arraySize) {
        int array[] = new int[arraySize];
  
        for (int i = 0; i < arraySize; i++) {
          array[i] = nextInt();
        }
  
        return array;
      }
  
      public long nextLong() {
        int c = read();
  
        while (isSpaceChar(c)) {
          c = read();
        }
  
        int sign = 1;
  
        if (c == '-') {
          sign = -1;
  
          c = read();
        }
  
        long result = 0;
  
        do {
          if (c < '0' || c > '9') {
            throw new InputMismatchException();
          }
  
          result *= 10;
          result += c & 15;
  
          c = read();
        } while (!isSpaceChar(c));
  
        return result * sign;
      }
  
      public long[] nextLongArray(int arraySize) {
        long array[] = new long[arraySize];
  
        for (int i = 0; i < arraySize; i++) {
          array[i] = nextLong();
        }
  
        return array;
      }
  
      public float nextFloat() {
        float result, div;
        byte c;
  
        result = 0;
        div = 1;
        c = (byte) read();
  
        while (c <= ' ') {
          c = (byte) read();
        }
  
        boolean isNegative = (c == '-');
  
        if (isNegative) {
          c = (byte) read();
        }
  
        do {
          result = result * 10 + c - '0';
        } while ((c = (byte) read()) >= '0' && c <= '9');
  
        if (c == '.') {
          while ((c = (byte) read()) >= '0' && c <= '9') {
            result += (c - '0') / (div *= 10);
          }
        }
  
        if (isNegative) {
          return -result;
        }
  
        return result;
      }
  
      public double nextDouble() {
        double ret = 0, div = 1;
        byte c = (byte) read();
  
        while (c <= ' ') {
          c = (byte) read();
        }
  
        boolean neg = (c == '-');
  
        if (neg) {
          c = (byte) read();
        }
  
        do {
          ret = ret * 10 + c - '0';
        } while ((c = (byte) read()) >= '0' && c <= '9');
  
        if (c == '.') {
          while ((c = (byte) read()) >= '0' && c <= '9') {
            ret += (c - '0') / (div *= 10);
          }
        }
  
        if (neg) {
          return -ret;
        }
  
        return ret;
      }
  
      public String next() {
        int c = read();
  
        while (isSpaceChar(c)) {
          c = read();
        }
  
        StringBuilder res = new StringBuilder();
  
        do {
          res.appendCodePoint(c);
  
          c = read();
        } while (!isSpaceChar(c));
  
        return res.toString();
      }
  
      public boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
  
      public String nextLine() {
        int c = read();
  
        StringBuilder result = new StringBuilder();
  
        do {
          result.appendCodePoint(c);
  
          c = read();
        } while (!isNewLine(c));
  
        return result.toString();
      }
  
      public boolean isNewLine(int c) {
        return c == '\n';
      }
  
      public void close() {
        try {
          stream.close();
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
  
      public InputReader(InputStream stream) {
        this.stream = stream;
      }
  
    }
  
    Template(InputStream inputStream, OutputStream outputStream) {
      InputReader in = new InputReader(inputStream);
      PrintWriter out = new PrintWriter(outputStream);
      Thread thread = new Thread(null, new Solver(in, out), "Solver", 1 << 29);
  
      try {
        thread.start();
        thread.join();
      } catch (InterruptedException e) {
        e.printStackTrace();
      } finally {
        in.close();
        out.flush();
        out.close();
      }
    }
  
    static class CMath {
  
      public static long power(long number, long power) {
        if (number == 1 || number == 0 || power == 0) {
          return 1;
        }
  
        if (power == 1) {
          return number;
        }
  
        if (power % 2 == 0) {
          return power(number * number, power / 2);
        } else {
          return power(number * number, power / 2) * number;
        }
      }
  
      public static long modPower(long number, long power, long mod) {
        if (number == 1 || number == 0 || power == 0) {
          return 1;
        }
  
        number = mod(number, mod);
  
        if (power == 1) {
          return number;
        }
  
        long square = mod(number * number, mod);
  
        if (power % 2 == 0) {
          return modPower(square, power / 2, mod);
        } else {
          return mod(modPower(square, power / 2, mod) * number, mod);
        }
      }
  
      public static long moduloInverse(long number, long mod) {
        return modPower(number, mod - 2, mod);
      }
  
      public static long mod(long number, long mod) {
        return number - (number / mod) * mod;
      }
  
      public static long modAdd(long mod, long... arr) {
        long sum = 0;
        for (long l : arr) {
          sum = CMath.mod(sum + l, mod);
        }
        return sum;
      }
  
      public static int gcd(int a, int b) {
        if (b == 0) {
          return a;
        } else {
          return gcd(b, a % b);
        }
      }
  
      public static long gcd(long a, long b) {
        if (b == 0) {
          return a;
        } else {
          return gcd(b, a % b);
        }
      }
  
      public static long min(long... arr) {
        long min = arr[0];
  
        for (int i = 1; i < arr.length; i++) {
          min = Math.min(min, arr[i]);
        }
  
        return min;
      }
  
      public static long max(long... arr) {
        long max = arr[0];
  
        for (int i = 1; i < arr.length; i++) {
          max = Math.max(max, arr[i]);
        }
  
        return max;
      }
  
      public static int min(int... arr) {
        int min = arr[0];
  
        for (int i = 1; i < arr.length; i++) {
          min = Math.min(min, arr[i]);
        }
  
        return min;
      }
  
      public static int max(int... arr) {
        int max = arr[0];
  
        for (int i = 1; i < arr.length; i++) {
          max = Math.max(max, arr[i]);
        }
  
        return max;
      }
  
    }
  
    public static void main(String[] args) {
      new Template(System.in, System.out);
    }
  
  }
  
  /*
  
  1
  3 1
  
  */
  