← 返回题目列表

AtCoder · typical90_be

057. 翻盖(★6)

中文机器翻译题面 查看原题

配点: 6 点

問題文

1, 2, \dots, M 编号为... M 张面板,所有面板最初都是背面朝上。同时,你面前有 1, 2, \dots, N 编号为... N 个开关。按下开关 i 会发生以下情况。

  • T_i 张面板 A_{i,1} ,\dots, A_{i,T_i} 会翻转,正反面会改变。

在这里,一旦按下的开关就无法再按第二次。

你的工作是将这 M 块面板的正反面按照希望摆放。需要注意的是,希望是长度为 M 可以得到第 0, 1 的序列 S 由下式给出S_j=0 表示将面板 j 翻到反面,S_j=1 表示将面板 j 翻到正面。

按按钮的方式有很多种,但如果不考虑按的顺序 2^N 的话,共有这样多种情况,在其中满足希望的按按钮方式有多少种呢。不过,答案可能会非常大, 998244353 后的余数。

制約

  • 1 \leq N,M \leq 300
  • 1 \leq T_i \leq M
  • 1 \leq A_{i,1} < \dots < A_{i,T_i} \leq M
  • S_i=0 或 至少 S_i=1
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
T_1
A_{1,1} \cdots A_{1,T_1}
\vdots
T_N
A_{N,1} \cdots A_{N,T_N}
S_1 \cdots S_M

出力

满足希望的按按钮方式的数量为 998244353 输出除以后的余数。


入力例 1

2 3
2
1 2
2
2 3
1 0 1

出力例 1

1

开关 按住 1 ,通过按下开关 2 的按钮, 3 张面板可以按希望的方式调整正反面。此外,除此之外 3 张面板不能按希望调整,因此答案是 1 是的。 请注意,我们正在寻找除以


入力例 2

2 3
1
1
1
2
0 1 1

出力例 2

0

面板 3 的正反面没有开关,所以面板 3 不能调整为正面。因此,答案是 0 是的。 请注意,我们正在寻找除以


入力例 3

3 2
1
1
1
2
1
2
1 0

出力例 3

2

2 张面板按希望调整的开关按钮的按法如下 2 方法有很多。

  • 开关 按住 1 仅按下这些按钮。
  • 开关 按住 1, 2, 3 的所有按钮。 对于写有

入力例 4

13 6
3
1 3 5
3
1 4 5
4
3 4 5 6
2
2 5
4
1 2 3 5
3
3 4 6
3
4 5 6
6
1 2 3 4 5 6
4
1 3 5 6
3
1 2 4
3
1 5 6
4
1 2 3 4
1
5
1 0 0 1 0 0

出力例 4

128