#1076. 关键的 Guan

Guan有 把编号为 的钥匙。这些钥匙中有一些是真钥匙，而其他是假的。

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

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

Guan插入了 把钥匙 到 X 门中。测试结果用一个英文字母 表示：

• 表示在第 次测试中 X 门打开了。
• 表示在第 次测试中 X 门没有打开。

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

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

第一行包括三个正整数 ，含义如题面描述。

接下来 行，每行描述一次测试。第一个整数 表示第 次测试有 把要是，接下来 表示用了 行的钥匙，最后一个字符 代表测试结果。

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

样例 1

输入

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

输出

2

样例 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

样例 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

输出

8

对于 的数据，满足：

• 和 是整数。

• 如果 ，则

• 是 'o' 或 'x'