C. Moamen и XOR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Moamen и Ezzat играют в игру. Они создают массив $$$a$$$ длины $$$n$$$, состоящий из неотрицательных целых чисел, где каждый элемент меньше $$$2^k$$$.

Moamen победит, если $$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$$$.

Здесь $$$\&$$$ обозначает операцию битового И, а $$$\oplus$$$ обозначает операцию битового исключающего ИЛИ.

Теперь Moamen хочет узнать, сколько существует таких массивов $$$a$$$, где он побеждает?

Так как ответ может быть очень большим, выведите его по модулю $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Входные данные

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 5$$$)— количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n\le 2\cdot 10^5$$$, $$$0 \le k \le 2\cdot 10^5$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество различных массивов, в которых Moamen победит.

Выведите результат по модулю $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Пример
Входные данные
3
3 1
2 1
4 0
Выходные данные
5
2
1
Примечание

В первом примере $$$n = 3$$$, $$$k = 1$$$. В результате все возможные массивы — это $$$[0,0,0]$$$, $$$[0,0,1]$$$, $$$[0,1,0]$$$, $$$[1,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$ и $$$[1,1,1]$$$.

Moamen победит только в $$$5$$$ из них: $$$[0,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$, $$$[1,1,1]$$$.