You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

北辰OI俱乐部刚刚装修完, 愚蠢的人类工人设计了一种奇怪的开关风扇的方式

题目描述

有 $m$ 台风扇, 编号为 $1$ 到 $m$ , 另外有 $n$ 个开关， 编号为 $1$ 到 $n$ . 每个开关有两种状态 开 和 关 。 每台风扇可能被多个开关控制，第 $i$ 台风扇会被 $k_i$ 个开关控制，编号为 $a_{i1}, a_{i2}, ... a_{ik}$ 。

风扇运行的状态与开关按下的数量模 $2$ 有关, 如果余数为 $p_i$ , 则风扇状态为 运行 , 否则为 停止 .

问一共有多少种开关的 开 和 关 组合方式, 使得所有的风扇全部在 运行 状态

数据格式

输入格式

第一行两个整数 $n, m$,

接下来 $m$ 行, 每行第一个数字为 $k_i$ , 表示第 $i$ 台风扇被 $k_i$ 个开关控制, 接下来 $k_i$ 个数字 $a_{i1}, a_{i2}, ... a_{ik}$ 表示哪些开关控制该风扇.

最后一行 $m$ 个整数 $p_i$ .

输出格式

输出一个整数表示一共有多少种不同的方案.

样例

2 2
2 1 2
1 2
0 1

1

样例1解释

在1号开关为 开 , 2号开关为 开 的状态时, 所有风扇 运行 .

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

0

5 2
3 1 2 5
2 2 3
1 0

8

数据范围

$1<= n, m <= 10$

$1 <= k_i, s_{ij}, <= n$

$0 <= p_i <= 1$