有一个长度为$n$的三进制串$s$(每个字符都是0，1或者2)。现在有$m$个限制，其中第$i$个是：$s$里面第$l_i$个位置到第$r_i$个位置里恰好有$x_i$个不同的字符。
0
1
2
现在给出这$m$个限制，求出这样的字符串有多少个，对$10^9+7$取模。
输入有多组数据。第一行有一个整数$T$，表示测试数据组数。然后对于每组数据：
第一行包含两个整数$n$和$m$ ($1 \le n \le 5000, 0 \le m \le 10^6$)，表示字符串长度和限制个数。
接下来$m$行，每行包含三个整数$l_i$，$r_i$和$x_i$ ($1 \le l_i \le r_i \le n, 1 \le x_i \le 3$)。
保证所有数据中$n$的和不超过$5000$，所有$m$的和不超过$10^6$。
对于每组数据，输出一个整数，代表字符串个数对$10^9+7$取模后的值。
4 1 0 2 0 3 0 5 2 1 3 3 4 5 1
3 9 27 18
Comet OJ