Dr. Mitko Dimitrov 正在筹划队内训练，以帮助他的学生们备战下一届区域赛。他希望所有学生都能获得共同训练的经验，以便交流知识，并避免整个队伍同时毕业而导致来年无人可用的尴尬局面。

为了便于训练，他预订了一个双区房间，学生们可以在两个独立的队伍（A 队 and B 队）中进行训练。这使他能够同时监督两支队伍，并指导学生更换队伍，从而让他们获得与不同人合作的经验。训练将分为若干个时长一小时的场次，他可以指导少数学生在各场次之间的休息时间更换队伍。然而，他希望在第一场和最后一场训练中，所有人都在 A 队，以便在开始时讲解训练内容，并在结束时进行总结。

每个学生根据其特长可以被归类为解题手（problem solver）或代码手（problem coder）之一（但不能同时是两者）。为了减少人员流动，Dr. Dimitrov 在场次之间的休息时间里，每种类型的学生至多只会指导一名更换队伍。

Dr. Dimitrov 还准备了少量的挑战题，他计划在训练期间的不同时间点将这些题目分发给特定的队伍。由于题目的难度各不相同，他预先确定了在某场训练中解决该题所需的解题手和代码手的数量。此外，解决该题可能还需要一个总人数的下限，该下限可能大于所需解题手和代码手数量之和。Dr. Dimitrov 希望合理安排队伍人员，使得所有挑战题在训练期间都能被成功解决。

请注意，一个队伍在同一场次中可能会被分配多道挑战题，如果该队伍的人员构成满足每道题的要求，他们就可以在同一场次中解决所有这些题目。例如，在样例 1 中，一个拥有 6 名解题手和 5 名代码手的队伍可以在同一场次中解决第二道和第三道题目。

Dr. Dimitrov 有多少种指导学生更换队伍的方式，以确保满足所有约束条件？输出答案对 $10^9 + 7$ 取模的结果。如果存在某个场次，在一种方案中某个特定的学生被要求更换队伍，而在另一种方案中没有，则这两种方案被视为是不同的。

输入格式

第一行包含 4 个整数：$N$ ($3 \le N \le 10^{18}$)，表示训练的场次数量；$P$ ($1 \le P \le 5$)，表示挑战题的数量；$S$ ($1 \le S \le 35$)，表示解题手的数量；$C$ ($1 \le C \le 35$)，表示代码手的数量。

接下来的 $P$ 行，每行描述一道挑战题。每行以一个整数 $t_i$ ($1 < t_i < N$) 和一个字符 $g_i$ ($g_i \in \{A, B\}$) 开始，表示第 $i$ 道挑战题在第 $t_i$ 场训练中被分配给队伍 $g_i$。请注意，Dr. Dimitrov 不会在第一场和最后一场训练中分发挑战题。

该行的其余部分包含三个整数，描述解决该挑战题所需的人员：$s_i$ ($0 \le s_i \le S$)、$c_i$ ($0 \le c_i \le C$) 和 $b_i$ ($\max(1, s_i + c_i) \le b_i \le S + C$)，表示第 $i$ 道挑战题需要 $s_i$ 名解题手、$c_i$ 名代码手，且总共至少需要 $b_i$ 名解题手和代码手。

挑战题按场次非递减的顺序给出。

输出格式

输出在满足约束条件的前提下，Dr. Dimitrov 指导学生更换队伍的方案数对 $10^9 + 7$ 取模后的结果。

样例

输入样例 1

4 3 7 5
2 B 1 1 2
3 A 0 5 6
3 A 6 2 8

输出样例 1

70

输入样例 2

8 2 5 3
6 A 4 2 7
7 B 2 1 3

输出样例 2

0

输入样例 3

10 2 3 4
3 A 1 2 4
6 B 2 1 3

输出样例 3

289313785

输入样例 4

1000000000000000000 2 4 4
500000000000000000 A 2 1 4
500000000000000000 B 1 2 4

输出样例 4

759384011

说明

样例 1 说明

在此测试用例中，有 7 名解题手和 5 名代码手。在第 1 场训练中，所有人都在 A 队。在第 2 场训练中，B 队有一道挑战题，需要每种类型的学生各至少 1 名。Dr. Dimitrov 必须此时选择 7 名解题手中的 1 名和 5 名代码手中的 1 名派往 B 队。在第 3 场训练中，前往 B 队的代码手必须返回 A 队，以协助解决那里的两道挑战题中的第一道。前往 B 队的解题手不需要立即返回，因此他们可以在第 3 场或第 4 场训练时返回 A 队。在第 4 场训练中，所有人再次聚在一起。

答案为 $7 \cdot 5 \cdot 2 = 70$（考虑选择哪位解题手和哪位代码手前往 B 队，以及解题手在什么时间返回 A 队）。