You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Guan有 $N$ 把编号为 $1,2,\ldots,N$ 的钥匙。这些钥匙中有一些是真钥匙，而其他是假的。

有一扇门，X 门，Guan可以插入任意数量的钥匙。只有当插入的真钥匙数量至少为 $K$ 时，X 门才会打开。

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

Guan插入了 $C_i$ 把钥匙 $A_{i,1}, A_{i,2}, \ldots, A_{i,C_i}$ 到 X 门中。测试结果用一个英文字母 $R_i$ 表示：

• $R_i = o$ 表示在第 $i$ 次测试中 X 门打开了。
• $R_i = x$ 表示在第 $i$ 次测试中 X 门没有打开。

在这 $2^N$ 种可能的组合中，找到不与任何测试结果矛盾的组合的数量。

可能存在测试结果不正确的情况，没有任何组合满足条件。在这种情况下，输出 $0$。

输入格式

第一行包括三个正整数 $N, M, K$ ，含义如题面描述。

接下来 $M$ 行，每行描述一次测试。第一个整数 $C_i$ 表示第 $i$ 次测试有 $C_i$ 把要是，接下来 $A_{i,1}, A_{i,2}, \dots, A_{i, C_i}$ 表示用了 $A_i$ 行的钥匙，最后一个字符 $R_i$ 代表测试结果。

输出格式

输出一个整数，表示不与任何测试结果矛盾的组合的数量。

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

2

【样例 1 解释】

在此输入中，有三把钥匙并进行了两次测试。打开 X 门需要两把真钥匙。

在第一次测试中，使用了钥匙 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 \leq K \leq N \leq 15$
• $1 \leq M \leq 100$
• $1 \leq C_i \leq N$
• $1 \leq A_{i,j} \leq N$
• 如果 $j \ne k$，则 $A_{i,j} \ne A_{i,k}$
• $R_i$ 是 'o' 或 'x'