Pizza#8267
Vasya is planning to make a pizza for of his friends. He has additional ingredients available, each of which can either be included in the pizza or left out. Vasya can choose to use all the ingredients or none at all, resulting in 2^n possible combinations for the pizza.
However, not every combination will satisfy his friends. Each friend has a list of preferences, such as "I want the pizza to include ingredient " or "I want the pizza to exclude ingredient ". Fortunately, Vasya's friends are not overly demanding; a pizza that meets at least one preference from a friend's list will make that friend happy.
Vasya's goal is to create a pizza that satisfies at least one preference from each of his friends' lists.
Determine how many ways Vasya can make the pizza to ensure all his friends are pleased. Since this number can be very large, provide the result modulo .
The first line of input contains two integers and — 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 following lines corresponds to one of Vasya's friends and contains an integer a_i — the number of preferences in the list, followed by a_i numbers b_{i,j} — describing the preferences (1 \le a_i \le 100, -n \le b_{i,j} \le n, b_{i,j} \neq 0). If b_{i,j} is positive, it means the -th friend prefers the pizza to include ingredient b_{i,j}; if negative, the friend prefers the pizza to exclude ingredient -b_{i,j}.
No ingredient appears more than once in a single friend's list.
Output the number of different ways to make the pizza that would satisfy all of Vasya's friends, modulo .
Example 1
In the first example, the suitable ingredient sets are: (1), (3), (1; 3), (1; 4), (1; 3; 4).
In the second example, ingredient should not be included in the pizza, while the other ingredients can be included or not. The answer is the remainder of 2^{67} divided by .