AT_abc356_c [ABC356C] Keys

[problemUrl]: https://atcoder.jp/contests/abc356/tasks/abc356_c あなたは $ N $ 本の鍵 $ 1,2,\dots,N $ を持っています。 このうち何本かの鍵は正しい鍵で、それ以外はダミーの鍵です。 また、鍵を何本でも挿し込める ドアX があり、この ドアX は正しい鍵を $ K $ 本以上挿し込んだ時、またその時に限って開きます。 あなたはこれらの鍵に対して $ M $ 回のテストを行いました。このうち $ i $ 回目のテストの内容は次の通りです。 - $ C_i $ 本の鍵 $ A_{i,1},A_{i,2},\dots,A_{i,C_i} $ を ドアX に挿し込む。 - テスト結果はひとつの英文字 $ R_i $ で表現される。 - $ R_i\ = $ `o` のとき $ i $ 回目のテストでドアが開いたことを表す。 - $ R_i\ = $ `x` のとき $ i $ 回目のテストでドアが開かなかったことを表す。 各鍵が正しいかダミーかの組み合わせは $ 2^N $ 通り考えられますが、このうちどのテスト結果にも矛盾しない組み合わせの個数を求めてください。 ただし、与えられるテスト結果が誤っており上記の条件を満たす組み合わせが存在しない場合もあります。その場合は $ 0 $ 通りと解答してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ C_1 $ $ A_{1,1} $ $ A_{1,2} $ $ \dots $ $ A_{1,C_1} $ $ R_1 $ $ C_2 $ $ A_{2,1} $ $ A_{2,2} $ $ \dots $ $ A_{2,C_2} $ $ R_2 $ $ \vdots $ $ C_M $ $ A_{M,1} $ $ A_{M,2} $ $ \dots $ $ A_{M,C_M} $ $ R_M $

答えを整数として出力せよ。

### 制約 - $ N,M,K,C_i,A_{i,j} $ は整数 - $ 1\ \le\ K\ \le\ N\ \le\ 15 $ - $ 1\ \le\ M\ \le\ 100 $ - $ 1\ \le\ C_i\ \le\ N $ - $ 1\ \le\ A_{i,j}\ \le\ N $ - $ j\ \neq\ k $ ならば $ A_{i,j}\ \neq\ A_{i,k} $ - $ R_i $ は `o` または `x` ### Sample Explanation 1 この入力では鍵が $ 3 $ 本あり、テストは $ 2 $ 回行われました。 また、 ドアX を開くのに必要な正しい鍵の本数は $ 2 $ 本です。 - $ 1 $ 回目のテストでは鍵 $ 1,2,3 $ を使い、その結果 ドアX は開きました。 - $ 2 $ 回目のテストでは鍵 $ 2,3 $ を使い、その結果 ドアX は開きませんした。 各鍵が正しいかダミーかの組み合わせであって、どのテスト結果にも矛盾しないものは以下の $ 2 $ 通りです。 - 鍵 $ 1 $ は本物、鍵 $ 2 $ はダミー、鍵 $ 3 $ は本物である。 - 鍵 $ 1 $ は本物、鍵 $ 2 $ は本物、鍵 $ 3 $ はダミーである。 ### Sample Explanation 2 問題文中でも述べた通り、答えが $ 0 $ 通りである場合もあります。