城市动物园正在入口广场展示其多样的动物！广场上有一排 $N$ 个笼子，每个笼子可以容纳一只动物。动物园共有 $M$ 种动物，每种动物都有无限多只。饲养员每天会挑选 $N$ 只动物并安排它们填满所有笼子。然而，安排过程受到一些限制，每条限制要么是：(1) 两种类型的动物不能相邻放置，因为其中一种会捕食另一种；或者 (2) 特定的笼子不能放置某些类型的动物。请注意，由于自然界中存在同类相食的现象，两种相同类型的个体动物也可能无法相邻！

饲养员希望每天的动物展示配置都不相同。如果两个配置中任意一个笼子里的动物类型不同，则认为这两个配置不同。饲养员想知道总共有多少种不同的配置方案。请帮他计算一下！

输入格式

第一行包含三个整数 $N, M, K$ ($1 \le N \le 10^8, 1 \le M \le 50, 0 \le K \le 1000$)。$N$ 是笼子的数量，$M$ 是动物的种类数，$K$ 是限制条件的数量。

在接下来的 $K$ 行中，每行以一个字符 $t \in \{'A', 'B'\}$ 开头，表示限制类型。如果 $t$ 为 'A'，则后面跟着两个整数 $x, y$ ($1 \le x, y \le M$)，表示类型 $x$ 的动物不能与类型 $y$ 的动物相邻。所有 'A' 类限制给出的对都是不同的。更具体地说，$(a, b)$ 和 $(b, a)$ 被视为相同。

如果 $t$ 为 'B'，则后面跟着两个整数 $i, p$ ($1 \le i \le N, 1 \le p \le M$)，以及 $p$ 个不同的整数 $c_1, \dots, c_p$，表示笼子 $i$ 禁止放置的动物类型。每个笼子最多只有一条 'B' 类限制。

输出格式

输出一行，包含一个整数，表示不同配置的数量，结果对 $(10^9 + 7)$ 取模。

样例

样例输入 1

3 4 4
A 1 3
B 1 1 2
A 2 4
B 3 3 1 2 4

样例输出 1

7

样例输入 2

10 2 0

样例输出 2

1024

说明

在样例 1 中，有 3 个笼子和 4 种动物。类型 1 和 3 的动物不能相邻；类型 2 和 4 的动物不能相邻。笼子 1 不能放置类型 2 的动物；笼子 3 不能放置类型 1, 2, 4 的动物。唯一可能的配置是 (1,2,3), (3,2,3), (3,3,3), (4,3,3), (1,4,3), (3,4,3), (4,4,3)。