Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 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