C - Keys Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

あなたは 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_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

入力

入力は以下の形式で標準入力から与えられる。

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

出力

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

入力例 1

3 2 2
3 1 2 3 o
2 2 3 x

出力例 1

2

この入力では鍵が 3 本あり、テストは 2 回行われました。
また、 ドアX を開くのに必要な正しい鍵の本数は 2 本です。

  • 1 回目のテストでは鍵 1,2,3 を使い、その結果 ドアX は開きました。
  • 2 回目のテストでは鍵 2,3 を使い、その結果 ドアX は開きませんした。

各鍵が正しいかダミーかの組み合わせであって、どのテスト結果にも矛盾しないものは以下の 2 通りです。

  • 鍵 1 は本物、鍵 2 はダミー、鍵 3 は本物である。
  • 鍵 1 は本物、鍵 2 は本物、鍵 3 はダミーである。

入力例 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

出力例 2

0

問題文中でも述べた通り、答えが 0 通りである場合もあります。

入力例 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

出力例 3

8

Score : 300 points

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

  • You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
  • The test result is represented by a single English letter R_i.
    • R_i = o means that Door X opened in the i-th test.
    • R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

  • N, M, K, C_i, and A_{i,j} are integers.
  • 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
  • A_{i,j} \neq A_{i,k} if j \neq k.
  • R_i is o or x.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

2

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

  • In the first test, keys 1, 2, 3 were used, and Door X opened.
  • In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

  • Key 1 is real, key 2 is a dummy, and key 3 is real.
  • Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

0

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

Sample Output 3

8