小 $H$ 要用 $n+1$ 只骡子运送 $k$ 种物资。每只骡子可以任选物资运输（也可以选择运
输 $0$ 种物资）。
由于骡子并不是马，所以没有任何一种物资能够同时被第 $0\sim n-1$ 只这 $n$ 只骡子
运输。
由于骡子并不是马，所以第 $1 \sim n$ 这只骡子并不能运输全部的 $k$ 种物资。
根据以上原则，一共有多少种运输方案？

请给出答案对 $10^9+7$ 取模的结果。

对于所有数据，满足 $0 \le T \le 10^5, 3 \le n,k \le 10^8$。

分析

根据套路，我们可以将题目转化为网格图上的问题。

考虑题目要求 2，可以转化为至少有一列 $[1 \sim n]$ 全为 $0$ 的段，我们单独考虑。

对于剩下的情况，我们需要满足的性质：

• $[1 \sim n]$ 中至少有一个 $1$（避免与全 $0$ 重复）
• $[0 \sim n-1]$ 中至少有一个 $0$（题目要求 1）

---

---

由此我们可以得到式子：

---

然而这个式子直接做是 $O(k)$ 的，所以我们考虑化简。

发现这个式子长得很像二项式定理，考虑用二项式定理优化：

$$\sum_{i=1}^k\binom{k}{i} \times 2^i \times [(2^{n-1}-2)\times 4 + 2 + 2] ^ {k-i}$$

$$\sum_{i=1}^k\binom{k}{i} \times 2^i \times [(2^{n-1}-1)\times 4] ^ {k-i}$$

$$\sum_{i=1}^k\binom{k}{i} \times 2^i \times (2^{n+1}-4) ^ {k-i}$$

为了使用二项式定理，可以化为：

$$[\sum_{i=0}^k\binom{k}{i} \times 2^i \times (2^{n+1}-4) ^ {k-i}]-(2^{n+1}-4)^{k}$$

根据二项式定理，可化简为下面式子：

$$(2^{n+1}-2)^{k}-(2^{n+1}-4)^{k}$$

使用快速幂可以在 $O(\log_2 k)$ 的时间复杂度内解决本题。

代码很简单：

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int mod = 1e9 + 7;

int qpow(int a, int b) {
    int res = 1 % mod;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

signed main() {
    int _ = read();
    while (_ -- ) {
        int n = read(), k = read();
        int a = qpow(qpow(2, n + 1) - 2, k);
        int b = qpow(qpow(2, n + 1) - 4, k);
        printf("%lld\n", (a - b + mod) % mod);
    }
    return 0;
}