팀 연습

Team Practice Room

Dr. Mitko Dimitrov는 학생들이 다음 지역 대회를 준비할 수 있도록 팀 연습을 계획하고 있다. 그는 모든 학생이 함께 연습하는 경험을 쌓아 지식을 공유하고, 팀 전체가 한꺼번에 졸업하여 다음 해에 아무도 남지 않는 상황을 피하기를 바란다.

이 연습을 진행하기 위해 그는 학생들이 서로 분리된 두 팀(팀 A와 팀 B)으로 연습할 수 있는 분할된 방을 예약했다. 이를 통해 그는 두 팀을 동시에 감독하고, 학생들이 서로 다른 사람들과 협력하는 경험을 쌓도록 팀을 바꾸라고 지시할 수 있다. 연습은 한 시간 길이의 세션들로 진행되며, 그는 세션 사이에 소수의 학생에게 팀을 바꾸라고 지시할 수 있다. 하지만 연습을 설명하고 마지막에 마무리 논의를 하기 위해 첫 세션과 마지막 세션에는 모두가 팀 A에 함께 있기를 바란다.

각 학생은 강점에 따라 문제 해결자 또는 문제 코더 중 하나로 분류할 수 있다(둘 다일 수는 없다). 이동을 최소화하기 위해 Dr. Dimitrov는 세션 사이의 휴식 시간마다 각 유형의 학생을 최대 한 명씩 팀을 바꾸도록 지시한다.

Dr. Dimitrov는 연습 도중 여러 시점에 특정 팀에 제시할 소수의 도전 문제도 준비했다. 문제마다 난도가 다르므로, 그는 한 세션 동안 문제를 해결하는 데 필요한 문제 해결자와 문제 코더의 수를 미리 정해 두었다. 문제를 해결하는 데 필요한 전체 학생 수의 최솟값이 요구되는 해결자 수와 코더 수의 합보다 클 수도 있다. Dr. Dimitrov는 연습 중 모든 도전 문제가 해결되도록 팀을 구성하고자 한다.

한 팀이 같은 세션에 여러 도전 문제를 받을 수 있으며, 팀 구성이 각 문제의 요구 사항을 충족하면 그 문제들을 모두 해결할 수 있음에 유의하라. 예를 들어, 해결자가 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 \{ \text{A}, \text{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 설명

이 테스트 케이스에는 해결자가 7명, 코더가 5명 있다. 세션 1에는 모두가 팀 A에 함께 있다. 세션 2에는 각 유형의 학생이 한 명씩 필요한 도전 문제가 팀 B에 주어진다. Dr. Dimitrov는 그때 7명의 해결자 중 한 명과 5명의 코더 중 한 명을 골라 팀 B로 보내야 한다. 세션 3에는 팀 B로 갔던 코더가 팀 A의 두 도전 문제 중 첫 번째 문제를 푸는 데 도움을 주기 위해 팀 A로 돌아와야 한다. 팀 B로 갔던 해결자는 즉시 돌아올 필요가 없으므로, 세션 3 또는 세션 4에 팀 A로 돌아올 수 있다. 세션 4에는 모두가 다시 함께 있다.

답은 $7 \cdot 5 \cdot 2 = 70$이다(팀 B로 갈 해결자와 코더로 누구를 선택하는지, 그리고 해결자가 언제 팀 A로 돌아오는지를 고려하라).