Первыми словами маленького Бадави были «AND 0 большая сумма», поэтому он решил решить следующую задачу. Даны два целых числа \(n\) и \(k\), вычислите количество массивов длины \(n\), таких что:
- все элементы массива это целые числа от \(0\) до \(2^k-1\) (включительно);
- побитовое И всех его элементов это \(0\);
- сумма его элементов максимальная возможная.
Так как ответ может быть очень большим, выведите его остаток от деления на \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите количество массивов, удовлетворяющих всем условиям. Так как ответ может быть большим, выведите его остаток от деления на \(10^9+7\).
Примечание
В первом примере подходят \(4\) массива:
- \([3,0]\),
- \([0,3]\),
- \([1,2]\),
- \([2,1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 2
100000 20
|
4
226732710
|