题目描述

We have $N$ switches with "on" and "off" state, and $M$ bulbs. The switches are numbered $1$ to $N$, and the bulbs are numbered $1$ to $M$.

Bulb $i$ is connected to $k_i$ switches: Switch $s_{i1}$, $s_{i2}$, $...$, and $s_{ik_i}$. It is lighted when the number of switches that are "on" among these switches is congruent to $p_i$ mod $2$.

How many combinations of "on" and "off" states of the switches light all the bulbs?

我们有 $N$ 个处于 "开 "和 "关 "状态的开关和 $M$ 个灯泡。开关的编号为 $1$ 至 $N$ ，灯泡的编号为 $1$ 至 $M$ 。

灯泡 $i$ 连接到 $k_i$ 开关：开关 $s_{i1}$ 、 $s_{i2}$ 、 $...$ 和 $s_{ik_i}$ 。当这些开关中 "开 "的开关数与 $p_i$ 模 $2$ 全等时，灯亮。

有多少种开关 "开 "和 "关 "的状态组合能点亮所有灯泡？

输入格式

输入内容按以下格式标准输入：

$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

样例输入 #1

2 2
2 1 2
1 2
0 1

样例输出 #1

1

样例 #2

样例输入 #2

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

样例输出 #2

0

样例 #3

样例输入 #3

5 2
3 1 2 5
2 2 3
1 0

样例输出 #3

8

说明

数据规模与约定

• $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$ 。
• 所有输入值均为整数。

样例 $1$ 解释

• 当下列开关中 "开 "的开关数为偶数时，灯泡 $1$ 亮起：开关 $1$ 和 $2$ 。
• 当下列开关中 "开 "的开关数为奇数时，点亮灯泡 $2$ ：开关 $2$ .

开关 $1$ 、开关 $2$ 的状态有四种可能的组合：（开，开）、（开，关）、（关，开）和（关，关）。其中，只有（开，开）能点亮所有灯泡，因此我们应该打印 $1$ 。

样例 $2$ 解释

• 当下列开关中 "开 "的开关数为偶数时，灯泡 $1$ 亮起：开关 $1$ 和 $2$ 。
• 当下列开关中 "开 "的开关数为偶数时，点亮灯泡 $2$ ：开关 $1$ .
• 当下列开关中 "开 "的开关数为奇数时，点亮灯泡 $3$ ：开关 $2$ .

开关 $1$ 必须 "断开 "才能点亮灯泡 $2$ ，开关 $2$ 必须 "接通 "才能点亮灯泡 $3$ ，但这样灯泡 $1$ 就不会点亮。因此，不存在能点亮所有灯泡的开关状态组合，所以我们应该打印 $0$ 。