Chiaki 正在研究长度为 $n$ 的三进制字符串 $s$。三进制字符串是指仅由字符“0”、“1”和“2”组成的字符串。

Chiaki 设定了 $m$ 个限制条件，第 $i$ 个限制条件为：字符串 $s$ 从第 $l_i$ 位到第 $r_i$ 位（包含两端）的子串中，不同字符的数量恰好为 $x_i$。

Chiaki 想知道有多少个字符串满足这 $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$ 取模的结果。

样例

样例输入 1

4
1 0
2 0
3 0
5 2
1 3 3
4 5 1

样例输出 1

3
9
27
18

说明

在第四个样例中，所有可能的字符串为：21000, 12000, 20100, 02100, 10200, 01200, 21011, 12011, 20111, 02111, 10211, 01211, 21022, 12022, 20122, 02122, 10222, 01222。