暂无测试数据。

现在有 $n$ 个玩家在玩一个类似于狼人杀的游戏，其中有 $w$ 个人是狼，而余下的人都是村民，现在一共有 $m$ 次发言，每次发言可以攻击或保护一个玩家，已知两匹狼不会互相攻击，狼保护的玩家也一定是狼。没有一个玩家会被攻击或者保护超过一次，对于任何一次发言，$a < b$。DD 正在旁观这局游戏，现在已知 $m$ 次发言的情况，DD 想知道场上的角色分配一共有多少种可能的情况？

如果存在一人在情况 $a$ 中和情况 $b$ 中扮演不同的角色，就认为这两种情况不同。

输入格式

第一行三个整数，分别表示 $n,w,m$

接下来 $m$ 行，每行一个字符和两个整数，有下面两种可能

• $A\ a\ b$ 表示 $a$ 攻击 $b$
• $D\ a\ b$ 表示 $a$ 保护 $b$

输出格式

共一行，输出一共存在多少种情况，对 $10^9+7$ 取模

数据规模与约定

对于 $30\%$ 的数据，$1 \leq n \leq 20, 0 \leq m \leq 20$

对于 $60\%$ 的数据，$1 \leq n \leq 100, 0 \leq m \leq 100$

对于 $100\%$ 的数据，$1 \leq n \leq 200, 0 \leq m \leq 200$

3 2 2
A 1 2
D 1 3

2