Moamen 与异或

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Moamen 与 Ezzat 构造一个长度为 $n$ 的非负整数数组 $a$，其中每个元素都小于 $2^k$。

若

$$a_1\mathbin{\&}a_2\mathbin{\&}\cdots\mathbin{\&}a_n\ge a_1\oplus a_2\oplus\cdots\oplus a_n,$$

则 Moamen 获胜。求能使 Moamen 获胜的数组数量，答案对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $t$。

接下来 $t$ 行，每行包含两个整数 $n,k$。

输出格式

对每个测试用例输出一行答案。

样例输入 1

3
3 1
2 1
4 0

样例输出 1

5
2
1

数据范围

对于全部数据，$1\le t\le5$，$1\le n\le2\times10^5$，$0\le k\le2\times10^5$。

子任务编号	分值	特殊限制
1	30	$t\le3$ 且每组 $nk\le20$
2		所有测试用例的 $n$ 均为奇数
3	40	无特殊限制