有一个字符串 $s = s_1s_2 \dots s_n$。记子串 $s_i s_{i+1} \dots s_{i+l-1}$ 为二元组 $(i, l)$。Peter 知道关于字符串 $s$ 的一些事实，第 $i$ 条事实是子串 $(x_i, l_i)$ 与子串 $(y_i, l_i)$ 相等。

现在，Peter 想知道有多少个仅包含小写英文字母的字符串满足所有这些事实。答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入包含多个测试用例。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 200000$)，分别表示字符串的长度和事实的数量。

接下来 $m$ 行，每行包含三个整数 $x_i, y_i, l_i$ ($1 \le x_i, y_i, l_i \le n, \max\{x_i, y_i\} + l_i - 1 \le n$)。

所有测试用例中 $n$ 的总和不超过 $200000$，所有测试用例中 $m$ 的总和不超过 $200000$。

输出格式

对于每个测试用例，输出一个整数表示答案。答案必须对 $10^9 + 7$ 取模。

样例

样例输入 1

5 5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
8 3
1 4 3
3 4 1
4 6 3

样例输出 1

11881376
676