[Codeforces] 1557 C Moamen and XOR(组合数学)

Moamen and Ezzat are playing a game. They create an array a of n non-negative integers where every element is less than 2k.

Moamen wins if 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 1000000007 (109+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⋅105, 0≤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 1000000007 (109+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].

题意：

用 < 2k的数填充到长度为n的数组中，要使得数组中所有数& >= ^，问方案数

显然，当k == 1的时候，答案为1，只有当所有的数全为1的情况才可以满足题意

对于其他的情况{

用小于2k的数进行填充，那么说明填充的数字的二进制位数最多可以有k kk位，

从数的个数的角度来说，奇数个1^ 之后的结果是1，偶数个1^ 之后的结果是0，而对于0来讲，不管多少个0，^起来结果都是0

只要有一个0，那么说这一位上&之后就是0，而为了让^为0，那么只能够选择偶数个1

如果某一位上&为1，那么^为1的情况需要讨论n的奇偶性

{

当n为奇数，全1时&的结果是1，^的结果也是1

当n为偶数，全1时&的结果为1，^运算结果为0，这时显然这一位已经大于异或了，由于后面的权值小，所以可以任意选择

}

}

Code:

ll fact[maxn], infact[maxn];
void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= 200000; i++) {
        fact[i]   = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qPow(i, mod - 2) % mod;
    }
}
ll C(ll n, ll m) {
    return fact[n] * infact[n - m] % mod * infact[m] % mod;
}
ll n, m;
int main() {
    init();
    int T = read;
    while (T--) {
        ll ans = 0;
        n = read, m = read;
        if (m == 0) {
            puts("1");
            continue;
        }
        if (n % 2) {
            ans = qPow((qPow(2, n - 1) + 1) % mod, m);
            /**
            ll t = 1;
            for (int i = 0; i <= n - 1; i += 2) {
        t = (t + C(n,i)) % mod;
            }
            ans = qPow(t,m);
            **/
        } else {
            ll t = 0;
            /**
            for (int i = 0; i <= n - 2; i += 2) {
                t = (t + C(n, i)) % mod;
            }
            ans = qPow(t, m);
            **/
            t   = qPow(2, n - 1) - 1;
            ans = qPow(t, m);
            for (int i = 1; i <= m; i++) {
                ans = (ans + qPow(t, i - 1) * qPow(2, n * (m - i))) % mod;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

推荐博客：https://blog.csdn.net/zhouzi2018/article/details/119601507