P15863 [LBA-OI R3 C] wywmrfz

~~What a meaningless title! Are you problem testers obsessed with games?!!~~ So what? La la la~

Little Y has recently become obsessed with a tower defense game. Today, she focuses on a character, Little W. Little W can block **at most 2** enemies at the same time and perform several attacks. Each attack can be one of two types: 1. Normal attack: Deals 1 damage to all blocked enemies simultaneously. 2. Critical strike: Deals 2 damage to all blocked enemies simultaneously. Now, Little Y gives Little W $T$ tasks. In each task, Little W needs to attack exactly $n$ times to defeat $m$ enemies. The $i$-th enemy has health $k_i$ and **must** be defeated within the $l_i$-th to $r_i$-th attacks. Little Y will not make it too hard: Little W never needs to face 3 or more enemies at once. Little Y wants to know: **how many valid attack sequences** satisfy all requirements? Since the answer can be huge, you only need to output it modulo $10^9+7$. Two attack sequences are different if there exists an $i \in [1,n]$ such that one sequence uses a normal attack on the $i$-th step and the other uses a critical strike. ### Formal Statement Given positive integers $n$ and $m$ triples $(l, r, k)$, a sequence is called **good** if and only if: 1. All elements are in $\{1,2\}$. 2. For every $i \in [1,m]$, $\sum\limits_{j=l_i}^{r_i} a_j = k_i$. You need to find the number of good sequences modulo $10^9+7$. **Guarantee: Every position is covered by at most 2 intervals**, i.e. $$\forall i\in[1,n],\; \sum\limits_{j=1}^m \left[\,i\in[l_j,r_j]\,\right] \le 2$$ There are $T$ test cases in one test point.

The first line contains an integer $T$, the number of tasks. For each test case: - The first line contains two integers $n, m$. - The next $m$ lines each contain three integers $l, r, k$, representing the information of an enemy.

Output $T$ lines. Each line contains one integer: the answer for the $i$-th test case modulo $10^9+7$.

### Data Constraints | Test Case | $n \le$ | $m \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1\sim 2$ | $16$ | $32$ | None | | $3\sim 5$ | $36$ | $72$ | None | | $6\sim 7$ | $6000$ | $6000$ | Yes | | $8\sim 9$ | $6000$ | $2$ | None | | $10\sim 12$ | $200$ | $400$ | None | | $13\sim 15$ | $300$ | $600$ | None | | $16\sim 19$ | $3000$ | $6000$ | None | | $20\sim 25$ | $8000$ | $16000$ | None | **Special Property**: Every position is covered by at most 1 interval: $\forall i\in[1,n],\; \sum\limits_{j=1}^m \left[\,i\in[l_j,r_j]\,\right] \le 1$. For $100\%$ data: $1\le n\le 8000,\ 1\le m\le 2n,\ 1\le T\le 10$. **Hard Guarantee**: $\forall i\in[1,n],\; \sum\limits_{j=1}^m \left[\,i\in[l_j,r_j]\,\right] \le 2$.