钥匙

题目描述

你有编号为 $1, 2, \dots, N$ 的 $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_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$

输出格式

输出答案的整数。

样例

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

2

本输入中共有 3 把钥匙，进行了 2 次测试。

打开门 X 需要 2 把真钥匙。

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

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

与所有测试结果都不矛盾的真假钥匙组合有以下两种：

• 钥匙 1 为真，钥匙 2 为假，钥匙 3 为真。
• 钥匙 1 为真，钥匙 2 为真，钥匙 3 为假。

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

如题目描述所述，答案可能为 $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$
• 当 $j \neq k$ 时，$A_{i,j} \neq A_{i,k}$
• $R_i$ 为 o 或 x