#P18764. [2025NA]Team Practice

[2025NA]Team Practice

题目描述

某教练安排了连续 NN 节团队训练课,每节课对应一个时段。学生分成解题型与编码型两类,分别有 SS 人和 CC 人;每名学生仅属于其中一类。

训练时,学生分属 A、B 两组。第 11 节和第 NN 节课时,所有人都必须在 A 组。 每两节相邻课程之间,教练可以调整分组,但最多让一名解题型学生和一名编码型学生跨组移动;每一类也可以不移动任何人。

训练中有 PP 道挑战题,且会在指定时段交给指定组。每道题包含三项人数下限:

  • 该组解题型学生不少于 sis_i 人;
  • 该组编码型学生不少于 cic_i 人;
  • 该组学生总人数不少于 bib_i 人。

如果同一组在同一节课需要解决多道题,就必须同时满足每道题的要求。

求符合全部条件的学生换组安排数量,结果对 109+710^9+7 取模。若存在某一节课的换组安排中,至少一名具体学生的换组情况不同,则认为是两种不同方案。

输入格式

第一行包含四个整数 N,P,S,CN,P,S,C:

3≤N≤1018,1≤P≤5,3\le N\le10^{18},\quad1\le P\le5, 1≤S≤35,1≤C≤35.1\le S\le35,\quad1\le C\le35.

接下来 PP 行,每行依次给出

t_i g_i s_i c_i b_i

其意义与约束如下:

  • 1<ti<N1<t_i<N:挑战题安排的课次;
  • gig_i 为字符 A 或 B:接受这道题的组;
  • 0≤si≤S0\le s_i\le S、0≤ci≤C0\le c_i\le C:两类学生的最低要求;
  • max⁡(1,si+ci)≤bi≤S+C\max(1,s_i+c_i)\le b_i\le S+C:总人数的最低要求。

挑战题按照 tit_i 非递减的顺序给出,同一时段可能有多道题。

输出格式

输出一个整数:所有合法换组安排的数量对 109+710^9+7 取模后的结果。

样例 1

输入

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

输出

70

说明:第 2 节课需要 B 组各有一名不同类型的学生,共有 7×57\times5 种选人方法。编码型学生须在第 3 节课前返回 A 组,解题型学生则可以在第 3 或第 4 节课前返回,所以得到 7×5×2=707\times5\times2=70。

样例 2

输入

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

输出

0

样例 3

输入

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

输出

289313785

样例 4

输入

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

输出

759384011