Наборы специй для плова
Повар из Узгена готовит плов и хранит n баночек со смесями специй. Каждая смесь задана битовой маской a[i] из B бит: бит j равен 1, если в смеси есть специя номер j (зира, барбарис, кориандр, …).
Если высыпать в казан несколько смесей, в плове окажутся только те специи, которые есть во всех выбранных смесях (так уж устроены узгенские специи), то есть результат — побитовое И (AND) масок.
Для каждого из q вопросов x найдите, сколько существует непустых наборов баночек, побитовое И масок которых равно ровно x. Наборы различаются номерами баночек. Ответы выведите по модулю 10⁹ + 7.
Входные данные
В первой строке — B, n, q (1 ≤ B ≤ 20, 1 ≤ n ≤ 10⁶, 1 ≤ q ≤ 10⁵). Во второй строке — n чисел a[i] (0 ≤ a[i] < 2^B). В третьей — q чисел x (0 ≤ x < 2^B).
Выходные данные
Для каждого вопроса выведите количество наборов по модулю 10⁹ + 7.
Пример 1
Вход:
3 3 4
3 5 7
1 7 0 3
Выход:
2
1
0
2
Пояснение
Маски 3 (011), 5 (101), 7 (111). И равно 1 у наборов {3, 5} и {3, 5, 7}; равно 7 — только у набора {7}; равно 0 — ни у одного.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 15.
Подсказка
Посчитайте для каждой маски m число g[m] баночек, содержащих все специи из m (сумма по надмножествам). Тогда наборов с И, содержащим m, ровно 2^g[m] − 1, а дальше помогает формула включений-исключений по надмножествам.
Комментарии