该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有 $N$ 把编号为 $1, 2, \dots, N$ 的钥匙。
其中有些是正确的钥匙，其他的是虚假的钥匙。

有一扇门，记作门 $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$ 没有打开。

现在你需要计算出所有可能的钥匙正确性组合数，这些组合不会与任何测试结果矛盾。
如果给定的测试结果本身有误，导致不存在任何有效的组合，请输出 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$。
• 接下来的 $M$ 行，每行描述一次测试：
  • 第 $i$ 行的第一个整数 $C_i$ 表示第 $i$ 次测试中插入的钥匙数量。
  • 接着是 $C_i$ 个整数 $A_{i,1}, A_{i,2}, \dots, A_{i,C_i}$，表示插入的钥匙编号。
  • 最后是一个字符 $R_i$，表示测试的结果，$R_i$ 可以是 "o" 或 "x"。

输出格式

输出一个整数，表示满足条件的钥匙组合数。

样例

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

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

0

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

8

限制因素

• $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。

样例 $1$ 说明

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

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

有两种组合，哪把钥匙是真钥匙，哪把钥匙是假钥匙，测试结果都没有矛盾：

• 钥匙 $1$ 是真的，钥匙 $2$ 是假的，钥匙 $3$ 是真的。
• 密钥 $1$ 是真实的，密钥 $2$ 是真实的，密钥 $3$ 是假的。

样例 $2$ 说明

如问题陈述所述，答案可能是 $0$ 。