AT_abc356_c [ABC356C] Keys

你有 $N$ 个编号为 $1, 2, \dots, N$ 的密钥。 其中一些是真钥匙，其他都是假钥匙。 有一扇 X 门，你可以插入任意数量的钥匙。只有插入至少 $K$ 把真钥匙，X 门才会打开。 你已经对这些钥匙进行了 $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$ 。

#### 输入 输入内容由标准输入法提供，格式如下 >$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$ 、 $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$ 。