Score : $300$ points

问题陈述

你有 $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$ 次测试中门 X 打开了。
  • $R_i =$ x 表示在第 $i$ 次测试中门 X 没有打开。

有 $2^N$ 种可能的组合，哪些钥匙是真正的，哪些是假钥匙。在这些组合中，找出不与任何测试结果相矛盾的组合数量。 有可能给定的测试结果是错误的，没有任何组合满足条件。在这种情况下，报告 $0$。

以上为大语言模型 kimi 翻译，仅供参考。

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