B. AND 0, большая сумма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Первыми словами маленького Бадави были «AND 0 большая сумма», поэтому он решил решить следующую задачу. Даны два целых числа $$$n$$$ и $$$k$$$, вычислите количество массивов длины $$$n$$$, таких что:

  • все элементы массива это целые числа от $$$0$$$ до $$$2^k-1$$$ (включительно);
  • побитовое И всех его элементов это $$$0$$$;
  • сумма его элементов максимальная возможная.

Так как ответ может быть очень большим, выведите его остаток от деления на $$$10^9+7$$$.

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

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных.

В единственной строке каждого набора входных данных даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 20$$$).

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

Для каждого набора входных данных выведите количество массивов, удовлетворяющих всем условиям. Так как ответ может быть большим, выведите его остаток от деления на $$$10^9+7$$$.

Пример
Входные данные
2
2 2
100000 20
Выходные данные
4
226732710
Примечание

В первом примере подходят $$$4$$$ массива:

  • $$$[3,0]$$$,
  • $$$[0,3]$$$,
  • $$$[1,2]$$$,
  • $$$[2,1]$$$.