Moamen and Ezzat are playing a game. They create an array ??a of ??n non-negative integers where every element is less than 2??2k.
Moamen wins if ??1&??2&??3&…&????≥??1⊕??2⊕??3⊕…⊕????a1&a2&a3&…&an≥a1⊕a2⊕a3⊕…⊕an.
Here && denotes the bitwise AND operation, and ⊕⊕ denotes the bitwise XOR operation.
Please calculate the number of winning for Moamen arrays ??a.
As the result may be very large, print the value modulo 10000000071000000007 (109+7109+7).
Input
The first line contains a single integer ??t (1≤??≤51≤t≤5)— the number of test cases.
Each test case consists of one line containing two integers ??n and ??k (1≤??≤2?1051≤n≤2?105, 0≤??≤2?1050≤k≤2?105).
Output
For each test case, print a single value — the number of different arrays that Moamen wins with.
Print the result modulo 10000000071000000007 (109+7109+7).
Example
input
Copy
3
3 1
2 1
4 0
output
Copy
5
2
1
看到数据范围很大，于是借助类似数位dp的思想，考虑按位进行处理。设\(dp[i, 0]\)表示所有数第i位相与大于所有数第i位相异或的数的个数（假设没有第i + 1到第n位），\(dp[i, 1]\)表示所有数第i位相与等于所有数第i位相异或的数的个数。则输出的就是\((dp[k, 0] + dp[k, 1]) \% mod\)。考虑如何进行转移：因为相与和相异或本质上都只和n的奇偶性有关而不和n的大小有关，因此考虑用排列组合的方法进行计算。
当n为奇数：
- \(dp[i, 0] = 0\)。因为所有数第i位相与大于所有数第i位相异或的话只能n个数第i位全取1才有可能（否则相与结果必然为0，而相异或结果为0，必然不可能大于）此时所有数相与和相异或的结果都是1，方案数为0。
- \(dp[i, 1] =( C_n^0 + C_n^2 + C_n^4 +...+ C_n^{n - 1} + 1)\times (dp[i - 1,0] + dp[i - 1, 1])\)。因为此时有0，2，4.. n - 1个数为1的话相与和相异或都是0，再加上全为1的那一种，最后乘以dp[i - 1]的情况即可。因为当前位与和异或的相等，那么前一位（i - 1）的结果只能是大于或者等于。以及注意这些组合数的和等于\(2^{n - 1}\)
当n为偶数：
- \(dp[i, 0] = 2 ^ {(i - 1)\times n}\)，因为当前位结果大于，剩下所有位无论怎么取都可以。
- \(dp[i, 1] =( C_n^0 + C_n^2 + C_n^4 +...+ C_n^{n - 2})\times (dp[i - 1,0] + dp[i - 1, 1])\)
分析类似，注意\(C_n^0 + C_n^2 + C_n^4 +...+ C_n^{n - 2}=2^{n - 1} - 1\)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define int long long
#define mod 1000000007
using namespace std;
int n, k;
long long dp[200010][2];//大于 等于
long long fpow(long long a, long long b) {
long long ans = 1;
for(; b; b >>= 1) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
signed main() {
int t;
cin >> t;
while(t--) {
cin >> n >> k;
for(int i = 0; i <= n + 5; i++) {
dp[i][0] = dp[i][1] = 0;
}
if(k == 0) {
puts("1");
} else {
for(int i = 1; i <= k; i++) {
if(i == 1) {
if(n & 1) {
dp[i][0] = 0;
dp[i][1] = (fpow(2, n - 1) + 1) % mod;//加的1是1 1 1这样的 也算一样
} else {
dp[i][0] = 1;
dp[i][1] = (fpow(2, n - 1) - 1 + mod) % mod;
}
continue;
}
if(n & 1) {
dp[i][0] = 0;
dp[i][1] = (fpow(2, n - 1) + 1 + mod) % mod * (dp[i - 1][0] + dp[i - 1][1]) % mod;
} else {
dp[i][0] = fpow(2, (i - 1) * n) % mod;
dp[i][1] = (fpow(2, n - 1) - 1) % mod * (dp[i - 1][0] + dp[i - 1][1]) % mod;
}
}
cout << (dp[k][0] + dp[k][1]) % mod << endl;
}
}
return 0;
}