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.math.BigInteger;
  import java.util.*;
  
  /**
   * @author Mubtasim Shahriar
   */
  
  public class MoamenXor {
  
      static final long MOD = (long) 1e9 + 7;
      static final int maxn = (int) 2e5 + 10;
      static final long[] fact = new long[maxn];
      static final long[] factInverse = new long[maxn];
  
      public static void main(String[] args) {
  
          fact[0] = 1;
          for(int i = 1; i < maxn; i++) {
              fact[i] = mult(fact[i-1],i);
          }
  
          factInverse[maxn-1] = myPow(fact[maxn-1], MOD-2);
          for(int i = maxn-2; i >= 0; i--) {
              factInverse[i] = mult(factInverse[i+1], i+1);
          }
  
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          InputReader sc = new InputReader(inputStream);
          PrintWriter out = new PrintWriter(outputStream);
          Solver solver = new Solver();
  		int t = sc.nextInt();
  //        int t = 1;
          while (t-- != 0) {
              solver.solve(sc, out);
          }
          out.close();
  
      }
  
      private static long mult(long a, long b) {
          return a*b % MOD;
      }
  
      private static long myPow(long a, long b) {
          long ret = 1;
          while(b>0) {
              if(b%2!=0) {
                  ret = mult(ret, a);
              }
  
              a = mult(a,a);
              b /= 2;
          }
          return ret;
      }
  
      static class Solver {
          public void solve(InputReader sc, PrintWriter out) {
              int n = sc.nextInt();
              int k = sc.nextInt();
              if(k==0) {
                  out.println(1);
                  return;
              }
              long[][] dp = new long[k][2];
              long[] ncr = new long[n+1];
              ncr[0] = getNcR(n,0);
              for(int i = 2; i <= n; i++) {
                  ncr[i] = getNcR(n,i);
                  ncr[i] = add(ncr[i],ncr[i-2]);
              }
              if(n%2==1) {
                  dp[0][1] = add(ncr[n-1],1);
              } else {
                  dp[0][1] = ncr[n-2];
                  dp[0][0] = 1;
              }
              long pow2 = myPow(2,n);
              long nowpow2 = pow2;
              for(int bit = 1; bit < k; bit++) {
                  if(n%2==1) {
                      long nowWays = add(ncr[n-1],1);
                      dp[bit][1] = mult(nowWays,dp[bit-1][1]);
                  } else {
                      dp[bit][1] = mult(ncr[n-2],dp[bit-1][1]);
  
                      //meBigWays
                      long meBigWays = nowpow2;
  
                      //meEqualWays
                      long prevBigWays = dp[bit-1][0];
                      long meEqualWays = mult(ncr[n-2],prevBigWays);
  
                      dp[bit][0] = add(meBigWays,meEqualWays);
                  }
                  nowpow2 = mult(nowpow2,pow2);
              }
              out.println(add(dp[k-1][0],dp[k-1][1]));
          }
  
          private long add(long a, long b) {
              long ret = a+b;
              if(ret>=MOD) ret -= MOD;
              return ret;
          }
  
          private long getNcR(int n, int r) {
              long ret = fact[n];
              ret = mult(ret,factInverse[n-r]);
              ret = mult(ret,factInverse[r]);
              return ret;
          }
  
          private long modInverse(long a) {
              return myPow(a,MOD-2);
          }
  
      }
  
      static void sort(int[] arr) {
          Random rand = new Random();
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int idx = rand.nextInt(n);
              if (idx == i) continue;
              arr[i] ^= arr[idx];
              arr[idx] ^= arr[i];
              arr[i] ^= arr[idx];
          }
          Arrays.sort(arr);
      }
  
      static void sort(long[] arr) {
          Random rand = new Random();
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int idx = rand.nextInt(n);
              if (idx == i) continue;
              arr[i] ^= arr[idx];
              arr[idx] ^= arr[i];
              arr[i] ^= arr[idx];
          }
          Arrays.sort(arr);
      }
  
      static void sortDec(int[] arr) {
          Random rand = new Random();
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int idx = rand.nextInt(n);
              if (idx == i) continue;
              arr[i] ^= arr[idx];
              arr[idx] ^= arr[i];
              arr[i] ^= arr[idx];
          }
          Arrays.sort(arr);
          int l = 0;
          int r = n - 1;
          while (l < r) {
              arr[l] ^= arr[r];
              arr[r] ^= arr[l];
              arr[l] ^= arr[r];
              l++;
              r--;
          }
      }
  
      static void sortDec(long[] arr) {
          Random rand = new Random();
          int n = arr.length;
          for (int i = 0; i < n; i++) {
              int idx = rand.nextInt(n);
              if (idx == i) continue;
              arr[i] ^= arr[idx];
              arr[idx] ^= arr[i];
              arr[i] ^= arr[idx];
          }
          Arrays.sort(arr);
          int l = 0;
          int r = n - 1;
          while (l < r) {
              arr[l] ^= arr[r];
              arr[r] ^= arr[l];
              arr[l] ^= arr[r];
              l++;
              r--;
          }
      }
  
      static class InputReader {
          private boolean finished = false;
  
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
          private SpaceCharFilter filter;
  
          public InputReader(InputStream stream) {
              this.stream = stream;
          }
  
          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 peek() {
              if (numChars == -1) {
                  return -1;
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      return -1;
                  }
                  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 - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public long nextLong() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              long res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public String nextString() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              StringBuilder res = new StringBuilder();
              do {
                  if (Character.isValidCodePoint(c)) {
                      res.appendCodePoint(c);
                  }
                  c = read();
              } while (!isSpaceChar(c));
              return res.toString();
          }
  
          public boolean isSpaceChar(int c) {
              if (filter != null) {
                  return filter.isSpaceChar(c);
              }
              return isWhitespace(c);
          }
  
          public static boolean isWhitespace(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          private String readLine0() {
              StringBuilder buf = new StringBuilder();
              int c = read();
              while (c != '\n' && c != -1) {
                  if (c != '\r') {
                      buf.appendCodePoint(c);
                  }
                  c = read();
              }
              return buf.toString();
          }
  
          public String readLine() {
              String s = readLine0();
              while (s.trim().length() == 0) {
                  s = readLine0();
              }
              return s;
          }
  
          public String readLine(boolean ignoreEmptyLines) {
              if (ignoreEmptyLines) {
                  return readLine();
              } else {
                  return readLine0();
              }
          }
  
          public BigInteger readBigInteger() {
              try {
                  return new BigInteger(nextString());
              } catch (NumberFormatException e) {
                  throw new InputMismatchException();
              }
          }
  
          public char nextCharacter() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              return (char) c;
          }
  
          public double nextDouble() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              double res = 0;
              while (!isSpaceChar(c) && c != '.') {
                  if (c == 'e' || c == 'E') {
                      return res * Math.pow(10, nextInt());
                  }
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              }
              if (c == '.') {
                  c = read();
                  double m = 1;
                  while (!isSpaceChar(c)) {
                      if (c == 'e' || c == 'E') {
                          return res * Math.pow(10, nextInt());
                      }
                      if (c < '0' || c > '9') {
                          throw new InputMismatchException();
                      }
                      m /= 10;
                      res += (c - '0') * m;
                      c = read();
                  }
              }
              return res * sgn;
          }
  
          public boolean isExhausted() {
              int value;
              while (isSpaceChar(value = peek()) && value != -1) {
                  read();
              }
              return value == -1;
          }
  
          public String next() {
              return nextString();
          }
  
          public SpaceCharFilter getFilter() {
              return filter;
          }
  
          public void setFilter(SpaceCharFilter filter) {
              this.filter = filter;
          }
  
          public interface SpaceCharFilter {
              public boolean isSpaceChar(int ch);
          }
  
          public int[] nextIntArray(int n) {
              int[] array = new int[n];
              for (int i = 0; i < n; ++i) array[i] = nextInt();
              return array;
          }
  
          public int[] nextSortedIntArray(int n) {
              int array[] = nextIntArray(n);
              Arrays.sort(array);
              return array;
          }
  
          public int[] nextSumIntArray(int n) {
              int[] array = new int[n];
              array[0] = nextInt();
              for (int i = 1; i < n; ++i) array[i] = array[i - 1] + nextInt();
              return array;
          }
  
          public long[] nextLongArray(int n) {
              long[] array = new long[n];
              for (int i = 0; i < n; ++i) array[i] = nextLong();
              return array;
          }
  
          public long[] nextSumLongArray(int n) {
              long[] array = new long[n];
              array[0] = nextInt();
              for (int i = 1; i < n; ++i) array[i] = array[i - 1] + nextInt();
              return array;
          }
  
          public long[] nextSortedLongArray(int n) {
              long array[] = nextLongArray(n);
              Arrays.sort(array);
              return array;
          }
      }
  
  
  }
  