Problem K
Team Practice

Team Practice Room

Dr. Mitko Dimitrov is planning team practices to prepare his students for the next regional contest. He wants all of his students to get experience practicing together so that they can share knowledge and avoid the situation where the whole team graduates at once and leaves no one for the next year.

To facilitate this practice, he has booked a bifurcated room where students can practice in two separate teams (team A and team B). This allows him to monitor both teams simultaneously and to direct students to switch teams so that they can get experience working with different people. The practice will be held in hour-long sessions, and he can direct a small number of students to switch teams between sessions. However, he wants everyone to be together in team A for both the first and last sessions to explain the practice and to debrief at the end.

Each student can be classified as either a problem solver or a problem coder depending on their strengths (but not both). To minimize foot traffic, Dr. Dimitrov will direct at most one student of each type to switch teams during a break between sessions.

Dr. Dimitrov has also prepared a small number of challenge problems that he plans to present to specific teams at various points throughout the practice. As the problems have various difficulties, he has predetermined the number of problem solvers and problem coders that are needed to solve the problem during a session. There might also be a combined minimum number of students needed to solve the problem that is greater than the sum of the required number of solvers and coders. Dr. Dimitrov wants to structure the teams so that all challenge problems are solved during the practice.

Note that a team may be given multiple challenge problems for the same session, and that they can solve all of them if the team composition meets the requirements for each problem. For example, note that a team with 6 solvers and 5 coders can solve the second and third problems in the first sample input in one session.

How many ways can Dr. Dimitrov direct the students to switch teams to ensure that the constraints are met? Output your answer modulo $10^9+7$. Two ways are considered distinct if there is some session in which a specific student is asked to switch teams in one way and not in the other.

Input

The first line of input contains 4 integers—$N$ ($ 3 \le N \le 10^{18}$), the number of sessions in the practice, $P$ ($ 1 \le P \le 5$), the number of challenge problems, $S$ ($ 1 \le S \le 35$), the number of problem solvers, and $C$ ($ 1 \le C \le 35$), the number of problem coders.

Each of the next $P$ lines describes a challenge problem. The line begins with an integer $t_i$ ($1 < t_i < N$) and a character $g_i$ ($g_i \in \{ \text{A}, \text{B} \} $), indicating that the $i$-th challenge problem is presented to team $g_i$ during the $t_i$-th session in the practice. Note that Dr. Dimitrov will not hand out challenge problems during the first and last practice sessions. The rest of the line contains three integers describing which students are needed to solve the challenge problem: $s_i$ ($ 0 \le s_i \le S $), $c_i$ ($ 0 \le c_i \le C$), and $b_i$ ($ \max (1, s_i + c_i) \le b_i \le S+C$), which indicate that the $i$-th challenge problem requires $s_i$ problem solvers, $c_i$ problem coders, and at least $b_i$ solvers and coders in total.

The challenge problems are listed in non-decreasing order by session.

Output

Output the number of ways, modulo $10^9+7$, that Dr. Dimitrov can direct his students to switch teams within the constraints.

Explanation for sample 1

In this test case, there are 7 solvers and 5 coders. Everyone is together in team A during session 1. There is a challenge problem during session 2 for team B that needs one of each type of student. Dr. Dimitrov must pick one of the 7 solvers and one of the 5 coders to send to team B at that time. During session 3, the coder that went to team B must return to team A to help with the first of the two challenge problems there. The solver that went to team B does not need to return immediately, so they could return to team A for either session 3 or session 4. Everyone is together again during session 4.

The answer is $7 \cdot 5 \cdot 2 = 70$ (consider which solver and coder are selected to go to team B and at what time the solver comes back to team A).

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

70

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

0

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

289313785

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

759384011