시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 11 | 4 | 3 | 30.000% |
Vasya is going to bake a pizza for $m$ friends. There are $n$ additional ingredients at Vasya's disposal, each of which can either be put into pizza or not. Vasya may use all ingredients or even prepare a pizza without additional ingredients at all. Thus, there are $2^n$ possible pizza recipes.
Not just any pizza will make Vasya's friends happy, though. Every friends prepared a wish list of the form "ingredient $t$ should be included into the pizza" or "ingredient $t$ shouldn't be included into the pizza". Vasya's friends aren't too choosy: any pizza which has at least one of friend's wishes satisfied will make the friend happy.
Calculate the number of ways Vasya can bake the pizza to make all friends happy. Since this number may be too large, output it modulo $998244353$.
The first line of the input contains two integers $n$ and $m$ --- the number of ingredients and the number of Vasya's friends, respectively ($1 \le n \le 1000$, $1 \le m \le 20$).
Each of the next $m$ lines corresponds to one of Vasya's friend and contains an integer $a_i$ --- the number of wishes on the wish list, followed by $a_i$ integers $b_{i,j}$ --- the description of wishes on the list ($1 \le a_i \le 100$, $-n \le b_{i,j} \le n$, $b_{i,j} \neq 0$). If $b_{i,j}$ is positive, the $i$-th friend has a wish "ingredient $b_{i,j}$ should be included into the pizza", if it's negative, the $i$-th friend has a wish "ingredient $-b_{i,j}$ shouldn't be included into the pizza".
Every ingredient occurs at most once in every list.
Output the number of different pizzas making all friends happy, modulo $998244353$.
4 3 2 1 3 3 2 -4 1 1 -2
5
68 1 1 -42
468704809
In the first example, the following sets of ingredients will make all friends happy: $(1)$, $(3)$, $(1, 3)$, $(1, 4)$, $(1, 3, 4)$.
In the second example, ingredient $42$ shouldn't be included into the pizza, while all the other ingredients may be either included or not. The answer is equal to $2^{67}$ modulo $998244353$.