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\)).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество различных массивов, в которых Moamen победит.
Выведите результат по модулю \(1\,000\,000\,007\) (\(10^9 + 7\)).
Примечание
В первом примере \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1
2 1
4 0
|
5
2
1
|