开关与灯泡

题目描述

有 $N$ 个具有 on 和 off 两种状态的开关,以及 $M$ 个灯泡。开关编号为 $1$ 到 $N$,灯泡编号为 $1$ 到 $M$。

灯泡 $i$ 连接着 $k_i$ 个开关,当开关 $s_{i1}, s_{i2}, ..., s_{ik_i}$ 中处于 on 状态的开关个数除以 $2$ 的余数等于 $p_i$ 时,该灯泡点亮。

问:有多少种开关 on/off 状态的组合,能使所有灯泡都点亮?

输入格式

输入按以下格式从标准输入给出:

$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$

输出格式

输出能使所有灯泡都点亮的开关 on/off 状态组合的数量。

样例

2 2
2 1 2
1 2
0 1

1

• 灯泡 $1$ 在下列开关中有偶数个为 on 时点亮:开关 $1, 2$

• 灯泡 $2$ 在下列开关中有奇数个为 on 时点亮:开关 $2$

(开关 $1$、开关 $2$) 的状态可以是 (on,on)、(on,off)、(off,on)、(off,off),其中只有 (on,on) 满足条件,因此请输出 $1$。

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

0

• 灯泡 $1$ 在下列开关中有偶数个为 on 时点亮:开关 $1, 2$

• 灯泡 $2$ 在下列开关中有偶数个为 on 时点亮:开关 $1$

• 灯泡 $3$ 在下列开关中有奇数个为 on 时点亮:开关 $2$

要使灯泡 $2$ 点亮,开关 $1$ 必须为 off;要使灯泡 $3$ 点亮,开关 $2$ 必须为 on,但此时灯泡 $1$ 不亮。

因此,不存在能使所有灯泡都点亮的开关 on/off 状态组合,请输出 $0$。

5 2
3 1 2 5
2 2 3
1 0

8

数据范围

• $1 \le N, M \le 10$
• $1 \le k_i \le N$
• $1 \le s_{ij} \le N$
• $s_{ia} \neq s_{ib} \ (a \neq b)$
• $p_i$ 是 $0$ 或 $1$
• 输入均为整数