#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:360777216")
using LL = long long;
using ld = long double;
const int INF = 2 * 1000 * 1000 * 1000;
LL MOD = 1e9 + 7;
LL LINF = (LL)4e18;
double EPS = 1e-7;
using namespace std;
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
const LL max_er = 1e2;
vector<LL> min_div(max_er + 1, 0);
vector<int> pp(max_er + 1, 1);
vector<LL> res(max_er + 1, -1);
vector<LL> primes;
void eratosfen() {
  pp[0] = pp[1] = 0;
  for (LL i = 2; i <= max_er; ++i) {
    if (!pp[i]) continue;
    primes.push_back(i);
    min_div[i] = i;
    for (LL j = i * i; j <= max_er; j += i) {
      pp[j] = 0;
      if (!min_div[j]) min_div[j] = i;
    }
  }
}
vector<pair<int, int>> divs;
void get_divs(LL n) {
  while (n != 1) {
    LL cur = min_div[n];
    LL cnt = 0;
    while (n % cur == 0) {
      n /= cur;
      cnt++;
    }
    divs.push_back({cur, cnt});
  }
}
LL dp[200100][2];
vector<vector<int>> ress;
void gener(vector<int> &a, int n, int mx) {
  if (a.size() == n) {
    int and_val = 1, xor_val = 0;
    for (int(i) = 0; (i) < n; (i)++) {
      and_val &= a[i];
      xor_val ^= a[i];
    }
    if (and_val >= xor_val) ress.push_back(a);
    return;
  }
  for (int(i) = 0; (i) < mx; (i)++) {
    a.push_back(i);
    gener(a, n, mx);
    a.pop_back();
  }
}
LL bruteforce(LL n, LL k) {
  ress.clear();
  vector<int> aa;
  gener(aa, n, (1ll << k));
  return ress.size();
}
LL solve(LL n, LL k) {
  LL mod = 1e9 + 7;
  if (k == 0) return 1ll;
  memset(dp, 0, sizeof(dp));
  LL p2n = 1, p2n_1 = 1;
  for (int(i) = 0; (i) < n - 1; (i)++) {
    p2n_1 *= 2ll;
    p2n_1 %= mod;
  }
  p2n = p2n_1 * 2;
  p2n %= mod;
  if (n % 2 == 0) {
    dp[0][0] = (p2n_1 - 1 + mod) % mod;
    dp[0][1] = 1;
  } else {
    dp[0][0] = (p2n_1 + 1) % mod;
  }
  for (int(i) = 1; (i) < k; (i)++) {
    LL cur_eq = 0, cur_gt = 0;
    if (n % 2 == 0) {
      cur_eq = (p2n_1 - 1 + mod) % mod;
      cur_gt = 1;
    } else {
      cur_eq = (p2n_1 + 1) % mod;
      cur_gt = 0;
    }
    dp[i][1] =
        ((dp[i - 1][1] * p2n) % mod + (dp[i - 1][0] * cur_gt) % mod) % mod;
    dp[i][0] = (dp[i - 1][0] * cur_eq) % mod;
  }
  LL ans = (dp[k - 1][1] + dp[k - 1][0]) % mod;
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  srand(time(nullptr));
  LL __ = 1, n, m, k, r, g, b;
  cin >> __;
  for (int(_) = 0; (_) < __; (_)++) {
    cin >> n >> k;
    LL ans = solve(n, k);
    cout << ans << endl;
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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].

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:360777216")
using LL = long long;
using ld = long double;
const int INF = 2 * 1000 * 1000 * 1000;
LL MOD = 1e9 + 7;
LL LINF = (LL)4e18;
double EPS = 1e-7;
using namespace std;
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
const LL max_er = 1e2;
vector<LL> min_div(max_er + 1, 0);
vector<int> pp(max_er + 1, 1);
vector<LL> res(max_er + 1, -1);
vector<LL> primes;
void eratosfen() {
  pp[0] = pp[1] = 0;
  for (LL i = 2; i <= max_er; ++i) {
    if (!pp[i]) continue;
    primes.push_back(i);
    min_div[i] = i;
    for (LL j = i * i; j <= max_er; j += i) {
      pp[j] = 0;
      if (!min_div[j]) min_div[j] = i;
    }
  }
}
vector<pair<int, int>> divs;
void get_divs(LL n) {
  while (n != 1) {
    LL cur = min_div[n];
    LL cnt = 0;
    while (n % cur == 0) {
      n /= cur;
      cnt++;
    }
    divs.push_back({cur, cnt});
  }
}
LL dp[200100][2];
vector<vector<int>> ress;
void gener(vector<int> &a, int n, int mx) {
  if (a.size() == n) {
    int and_val = 1, xor_val = 0;
    for (int(i) = 0; (i) < n; (i)++) {
      and_val &= a[i];
      xor_val ^= a[i];
    }
    if (and_val >= xor_val) ress.push_back(a);
    return;
  }
  for (int(i) = 0; (i) < mx; (i)++) {
    a.push_back(i);
    gener(a, n, mx);
    a.pop_back();
  }
}
LL bruteforce(LL n, LL k) {
  ress.clear();
  vector<int> aa;
  gener(aa, n, (1ll << k));
  return ress.size();
}
LL solve(LL n, LL k) {
  LL mod = 1e9 + 7;
  if (k == 0) return 1ll;
  memset(dp, 0, sizeof(dp));
  LL p2n = 1, p2n_1 = 1;
  for (int(i) = 0; (i) < n - 1; (i)++) {
    p2n_1 *= 2ll;
    p2n_1 %= mod;
  }
  p2n = p2n_1 * 2;
  p2n %= mod;
  if (n % 2 == 0) {
    dp[0][0] = (p2n_1 - 1 + mod) % mod;
    dp[0][1] = 1;
  } else {
    dp[0][0] = (p2n_1 + 1) % mod;
  }
  for (int(i) = 1; (i) < k; (i)++) {
    LL cur_eq = 0, cur_gt = 0;
    if (n % 2 == 0) {
      cur_eq = (p2n_1 - 1 + mod) % mod;
      cur_gt = 1;
    } else {
      cur_eq = (p2n_1 + 1) % mod;
      cur_gt = 0;
    }
    dp[i][1] =
        ((dp[i - 1][1] * p2n) % mod + (dp[i - 1][0] * cur_gt) % mod) % mod;
    dp[i][0] = (dp[i - 1][0] * cur_eq) % mod;
  }
  LL ans = (dp[k - 1][1] + dp[k - 1][0]) % mod;
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  srand(time(nullptr));
  LL __ = 1, n, m, k, r, g, b;
  cin >> __;
  for (int(_) = 0; (_) < __; (_)++) {
    cin >> n >> k;
    LL ans = solve(n, k);
    cout << ans << endl;
  }
  return 0;
}

```