Определим преобразование P последовательности a1, a2, ..., an как b1, b2, ..., bn, где bi = a1 | a2 | ... | ai для всех i = 1, 2, ..., n. Символом | будем обозначать операцию побитового ИЛИ.
Вася поочередно применяет преобразование P ко всем последовательностям длины n из целых чисел от 1 до 2k - 1 включительно. Он хочет знать, для скольких последовательностей результат преобразования будет строго возрастающей последовательностью. Помогите ему посчитать это число по модулю 109 + 7.
Выходные данные
В единственной строке выведите количество подходящих последовательностей по модулю 109 + 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
|
3
|
|
2
|
2 3
|
30
|
|
3
|
3 3
|
48
|