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ドル$.