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: #include <bits/stdc++.h>
  #pragma GCC optimize("Ofast")
  #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
  #pragma GCC optimize("unroll-loops")
  using namespace std;
  long long MOD = 998244353;
  long long mod = 1000000007;
  double eps = 1e-12;
  double pi = acos(-1);
  mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
  template <typename T>
  T gcd(T a, T b) {
    return (b ? __gcd(a, b) : a);
  }
  template <typename T>
  T lcm(T a, T b) {
    return (a * (b / gcd(a, b)));
  }
  int add(int a, int b, int c = MOD) {
    int res = a + b;
    return (res >= c ? res - c : res);
  }
  int mod_neg(int a, int b, int c = MOD) {
    int res;
    if (abs(a - b) < c)
      res = a - b;
    else
      res = (a - b) % c;
    return (res < 0 ? res + c : res);
  }
  int mul(int a, int b, int c = MOD) {
    long long res = (long long)a * b;
    return (res >= c ? res % c : res);
  }
  int muln(int a, int b, int c = MOD) {
    long long res = (long long)a * b;
    return ((res % c) + c) % c;
  }
  long long mulmod(long long a, long long b, long long m = MOD) {
    long long q = (long long)(((long double)a * (long double)b) / (long double)m);
    long long r = a * b - q * m;
    if (r > m) r %= m;
    if (r < 0) r += m;
    return r;
  }
  template <typename T>
  T expo(T e, T n) {
    T x = 1, p = e;
    while (n) {
      if (n & 1) x = x * p;
      p = p * p;
      n >>= 1;
    }
    return x;
  }
  template <typename T>
  T power(T e, T n, T m = mod) {
    T x = 1, p = e;
    while (n) {
      if (n & 1) x = mul(x, p, m);
      p = mul(p, p, m);
      n >>= 1;
    }
    return x;
  }
  template <typename T>
  T extended_euclid(T a, T b, T &x, T &y) {
    T xx = 0, yy = 1;
    y = 0;
    x = 1;
    while (b) {
      T q = a / b, t = b;
      b = a % b;
      a = t;
      t = xx;
      xx = x - q * xx;
      x = t;
      t = yy;
      yy = y - q * yy;
      y = t;
    }
    return a;
  }
  template <typename T>
  T mod_inverse(T a, T n = MOD) {
    T x, y, z = 0;
    T d = extended_euclid(a, n, x, y);
    return (d > 1 ? -1 : mod_neg(x, z, n));
  }
  const int FACSZ = 1;
  int fact[FACSZ], ifact[FACSZ];
  void precom(int c = MOD) {
    fact[0] = 1;
    for (long long i = 1; i < FACSZ; i++) fact[i] = mul(fact[i - 1], i, c);
    ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
    for (long long i = 0; i < FACSZ - 1; i++) {
      ifact[i] = mul(i + 1, ifact[i + 1], c);
    }
  }
  int ncr(int n, int r, int c = MOD) {
    return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
  }
  void solve() {
    long long n, k;
    cin >> n >> k;
    long long won[k + 1];
    long long lost[k + 1];
    long long draw[k + 1];
    if (n & 1) {
      won[1] = 0;
      draw[1] = (power(2LL, n - 1)) + 1;
      won[1] %= mod;
      draw[1] %= mod;
    } else {
      won[1] = 1;
      draw[1] = (power(2LL, n - 1)) - 1;
      lost[1] = (power(2LL, n - 1));
      won[1] %= mod;
      draw[1] %= mod;
      lost[1] %= mod;
    }
    for (long long i = 2; i < k + 1; i++) {
      if (n & 1) {
        won[i] = (power(2LL, n - 1) + 1) * (won[i - 1]);
        draw[i] = (power(2LL, n - 1) + 1) * (draw[i - 1]);
        won[i] %= mod;
        draw[i] %= mod;
      } else {
        won[i] = (won[i - 1] + lost[i - 1] + draw[i - 1]) +
                 (power(2LL, n - 1) - 1) * won[i - 1];
        draw[i] = (power(2LL, n - 1) - 1) * draw[i - 1];
        lost[i] = (power(2LL, n - 1) - 1) * lost[i - 1] +
                  (power(2LL, n - 1)) * (won[i - 1] + lost[i - 1] + draw[i - 1]);
        won[i] %= mod;
        draw[i] %= mod;
        lost[i] %= mod;
      }
    }
    if (k == 0) {
      cout << 1 << '\n';
    } else {
      cout << (won[k] + draw[k]) % mod << '\n';
    }
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long t;
    cin >> t;
    for (int it = 1; it <= t; it++) {
      solve();
    }
    return 0;
  }
  