[ABC356] C - Keys

C - Keys

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 300 分

题面

你有 把钥匙，编号为 。
其中，有一些是真实的钥匙，另一些是虚假的。

有一个门，门 X，你可以向其中插入任意数量的钥匙。只有当插入至少 把真实钥匙时，门 X 才会打开。

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

• 你向门 X 插入了 把钥匙 。
• 测试结果由一个英文字母 表示。
  • 若 o 则表示第 次测试中门 X 打开了。
  • 若 x 则表示第 次测试中门 X 没有打开。

有 种可能的组合方式，确定哪些钥匙是真实的，哪些是虚假的。在这些组合方式中，找出不与任何测试结果矛盾的组合数目。
有可能给定的测试结果是错误的，无法找到符合条件的任何组合。在这种情况下，请报告 。

限制条件

• 、、、 和 都为整数。
• 若 ，则 。
• 为 o 或 x。

---

输入

输入从标准输入中以以下格式给出：

输出

输出为一个整数。

---

输入样例 1

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

输出样例 1

2

在这个样例中，有三把钥匙并进行了两次测试。
需要至少两把正确的钥匙才能打开门 X。

• 在第一次测试中，使用了钥匙 ，门 X 打开了。
• 在第二次测试中，使用了钥匙 ，门 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

输出样例 2

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

输出样例 3

8