Піца#8267
Вася планує приготувати піцу для своїх друзів. У нього є додаткових інгредієнтів, кожен з яких можна додати в піцу або не додавати. Вася може використати всі інгредієнти або жодного з них. Таким чином, він може приготувати піцу 2^n різними способами.
Однак не кожна піца сподобається друзям Васі. Кожен друг має список побажань, який містить вимоги на кшталт «хочу, щоб піца була з інгредієнтом » або «хочу, щоб інгредієнта в піці не було». Друзі Васі не вибагливі, тому піца, яка враховує хоча б одне побажання зі списку друга, їх задовольнить.
Вася хоче приготувати піцу так, щоб хоча б одне побажання кожного з його друзів було виконано.
Визначте, скількома способами Вася може приготувати піцу, щоб задовольнити всіх своїх друзів. Оскільки це число може бути дуже великим, виведіть його залишок від ділення на .
У першому рядку вхідних даних знаходяться цілі числа і — кількість інгредієнтів і кількість друзів Васі відповідно (1 \le n \le 1000, 1 \le m \le 20).
Кожен з наступних рядків відповідає одному з друзів Васі і містить ціле число a_i — кількість побажань у списку, за яким слідує a_i чисел b_{i,j} — опис побажань у списку (1 \le a_i \le 100, -n \le b_{i,j} \le n, b_{i,j} \neq 0). Якщо b_{i,j} позитивне, то -й друг має побажання «хочу, щоб піца була з інгредієнтом b_{i,j}», якщо негативне, то -й друг має побажання «хочу, щоб інгредієнта -b_{i,j} в піці не було».
Жоден інгредієнт не входить до списку одного друга більше одного разу.
Виведіть кількість різних способів приготувати піцу, які задовольнять усіх друзів Васі, взяте по модулю .
Приклад 1
У першому прикладі підходять такі набори інгредієнтів: (1), (3), (1; 3), (1; 4), (1; 3; 4).
У другому прикладі інгредієнта не повинно бути в піці, а решта інгредієнтів можуть бути присутніми або ні. Відповідь дорівнює залишку від ділення на .