Pizza

Vasya is planning to make a pizza for m of his friends. He has n 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 t" or "I want the pizza to exclude ingredient t". 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 998244353.

Input Data

The first line of input contains two integers n and m — the number of ingredients and the number of Vasya's friends, respectively (1 ≤ n ≤ 1000, 1 ≤ m ≤ 20).

Each of the following m 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 ≤ a[i] ≤ 100, -n ≤ b[i,j] ≤ n, b[i,j] ̸= 0)**. If **b[i,j]** is positive, it means the **i**-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 Data

Output the number of different ways to make the pizza that would satisfy all of Vasya's friends, modulo 998244353.

Examples

Note

In the first example, the suitable ingredient sets are: (1), (3), (1; 3), (1; 4), (1; 3; 4).

In the second example, ingredient 42 should not be included in the pizza, while the other ingredients can be included or not. The answer is the remainder of 267 divided by 998244353.