问题描述

有$N$个开关，每个开关有“开”和“关”两种状态，还有$M$个灯泡。开关编号为$1$到$N$，灯泡编号为$1$到$M$。
灯泡$i$连接到$k_i$个开关：开关$s_{i1}, s_{i2}, ..., s_{ik_i}$。当这些开关中处于“开”状态的开关数量模$2$等于$p_i$时，灯泡$i$会被点亮。
有多少种开关的“开”和“关”状态的组合能够点亮所有灯泡？

约束条件

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

2 2
2 1 2
1 2
0 1

样例输出1

1

• 灯泡1在以下开关中有偶数个处于“开”状态时被点亮：开关1和2。
• 灯泡2在以下开关中有奇数个处于“开”状态时被点亮：开关2。
  开关（开关1, 开关2）有四种可能的状态组合：（开, 开）、（开, 关）、（关, 开）和（关, 关）。其中只有（开, 开）能点亮所有灯泡，因此输出1。

样例输入2

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

样例输出2

0

• 灯泡1在以下开关中有偶数个处于“开”状态时被点亮：开关1和2。
• 灯泡2在以下开关中有偶数个处于“开”状态时被点亮：开关1。
• 灯泡3在以下开关中有奇数个处于“开”状态时被点亮：开关2。
  为了点亮灯泡2，开关1必须为“关”；为了点亮灯泡3，开关2必须为“开”。但这样灯泡1将不会被点亮。因此，没有能够点亮所有灯泡的开关状态组合，输出0。

样例输入3

5 2
3 1 2 5
2 2 3
1 0

样例输出3

8