20622번 - Ternary String Counting 다국어

Chiaki studies ternary strings $s$ of lentgh $n$. A ternary string is a string consisting of characters "0", "1", and "2".

Chiaki has made $m$ restrictions, and the $i$-th restriction is: the number of distinct characters of the substring of $s$ from the $l_i$-th position to the $r_i$-th position (both inclusive) is exactly $x_i$.

Chiaki would like to know the number of strings which meet the $m$ restrictions.  As the number may be very large, you are only asked to calculate it modulo $10^9+7$.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \le 5000$, $0 \le m \le 10^6$): the length of the string and the number of restrictions.

Each of the next $m$ lines contains three integers, $l_i$, $r_i$, and $x_i$ ($1 \le l_i \le r_i \le n$, $1 \le x_i \le 3$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$, and the sum of $m$ over all test cases does not exceed $10^6$.

For each test case, output an integer denoting the number of such strings modulo $10^9+7$.

In the fourth sample, all possible strings are: $21000$, $12000$, $20100$, $02100$, $10200$, $01200$, $21011$, $12011$, $20111$, $02111$, $10211$, $01211$, $21022$, $12022$, $20122$, $02122$, $10222$, $01222$.