19749번 - Pizza 다국어

문제

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ドル$.

제한

힌트

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ドル$.