К сожалению, автор задачи не смог придумать интересную историю, поэтому он просто просит вас решить следующую задачу.
Дан массив \(a\), состоящий из \(n\) положительных целых чисел. Посчитайте количество подпоследовательностей, для которых побитовое \(\mathsf{AND}\) элементов в подпоследовательности имеет ровно \(k\) единичных битов в двоичном представлении. Ответ может быть большим, поэтому выведите его по модулю \(10^9+7\).
Напомним, что подпоследовательность массива \(a\) - это последовательность, которую можно получить из \(a\), удалив некоторые (возможно, ни одного) элементы. Например, \([1, 2, 3]\), \([3]\), \([1, 3]\) являются подпоследовательностями \([1, 2, 3]\), но \([3, 2]\) и \([4, 5, 6]\) - нет.
Обратите внимание, что \(\mathsf{AND}\) обозначает логическую операцию AND.
Выходные данные
Для каждого тестового случая выведите одно целое число - количество подпоследовательностей, у которых в двоичном представлении значение побитового \(\mathsf{AND}\) имеет ровно \(k\) установленных битов. Ответ может быть большим, поэтому выведите его по модулю \(10^9+7\).