问题描述

我们有 $N$ 个开关，有 "on" 和 "off" 两种状态，还有 $M$ 个灯泡。开关从 $1$ 编号到 $N$，灯泡从 $1$ 编号到 $M$。

灯泡 $i$ 连接到 $k_i$ 个开关：开关 $s_{i1}$，$s_{i2}$，...，$s_{ik_i}$。当这些开关中处于 "on" 状态的数量对 $2$ 取模后与 $p_i$ 相等时，灯泡才会亮。

有多少种开关的 "on" 和 "off" 状态的组合可以点亮所有的灯泡？

约束条件

• $1 \leq N, M \leq 10$
• $1 \leq k_i \leq N$
• $1 \leq s_{ij} \leq N$
• $s_{ia} \neq s_{ib} (a \neq b)$
• $p_i$ 是 $0$ 或 $1$。
• 输入中的所有值都是整数。

输入

输入数据从标准输入读取，输入格式如下：

$N$ $M$

$k_1$ $s_{11}$ $s_{12}$ $...$ $s_{1k_1}$

:

$k_M$ $s_{M1}$ $s_{M2}$ $...$ $s_{Mk_M}$

$p_1$ $p_2$ $...$ $p_M$

参见示例输入1。

输出

打印出所有能点亮所有灯泡的开关的 "on" 和 "off" 状态的组合数。

示例输入1

2 2
2 1 2
1 2
0 1

示例输出1

1

• 灯泡 1 只在以下开关中处于 "on" 状态的数量为偶数时亮：开关 1 和 2。
• 灯泡 2 只在以下开关中处于 "on" 状态的数量为奇数时亮：开关 2。

存在四种开关状态的组合 (开关 1，开关 2)：(on, on)，(on, off)，(off, on) 和 (off, off)。其中，只有 (on, on) 能点亮所有的灯泡，所以我们应该输出 1。

示例输入2

2 3
2 1 2
1 1
1 2
0 0 1

示例输出2

0

• 灯泡 1 只在以下开关中处于 "on" 状态的数量为偶数时亮：开关 1 和 2。
• 灯泡 2 只在以下开关中处于 "on" 状态的数量为偶数时亮：开关 1。
• 灯泡 3 只在以下开关中处于 "on" 状态的数量为奇数时亮：开关 2。

开关 1 必须处于 "off" 状态才能亮灯泡 2，而开关 2 必须处于 "on" 状态才能亮灯泡 3，但这样会导致灯泡 1 不亮。因此，没有任何一种开关状态的组合可以点亮所有的灯泡，所以我们应该输出 0。

示例输入3

5 2
3 1 2 5
2 2 3
1 0

示例输出3

8