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