103562: [Atcoder]ABC356 C - Keys

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

问题描述

你有 $N$ 把钥匙，编号为 $1, 2, \dots, N$。其中一些是真正的钥匙，而另一些是假钥匙。

有一扇门，称为门X，你可以向其中插入任意数量的钥匙。只有当插入至少 $K$ 把真正的钥匙时，门X才会打开。

你对这些钥匙进行了 $M$ 次测试。第 $i$ 次测试如下进行：

• 你向门X插入了 $C_i$ 把钥匙 $A_{i,1}, A_{i,2}, \dots, A_{i,C_i}$。
• 测试结果用一个英文字母 $R_i$ 表示：
  • $R_i =$ o 表示在第 $i$ 次测试中门X打开了。
  • $R_i =$ x 表示在第 $i$ 次测试中门X没有打开。

有 $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$
• $A_{i,j} \neq A_{i,k}$ 如果 $j \neq 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

在这个输入中，有三把钥匙，进行了两次测试。
需要两把正确的钥匙才能打开门X。

• 在第一次测试中，使用了钥匙 $1, 2, 3$，门X打开了。
• 在第二次测试中，使用了钥匙 $2, 3$，门X没有打开。

有两种钥匙组合不与任何测试结果相矛盾：

• 钥匙 $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