Migrated from Lutece 2568 数列计数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

定义一个长度为 $n$ 的整数数列为一个好数列，当且仅当其满足以下三个条件：

1. $a_1=a_n=1$
2. 当 $2\leq i\leq n-1$ 时，$0\leq a_i\leq 2$
3. 当 $2\leq i\leq n$ 时，$|a_i-a_{i-1}|\leq 1$

其中，$a_i$ 表示数列的第 $i$ 项，数列下标从 $1$ 开始一直到 $n$。

为了避免题目太简单影响到做题体验，再添加 $m$ 个限制条件，第 $j$ 个限制条件用三个数 $l_j,r_j,b_j$ 表示，意为数列的 $l_j$ 项到 $r_j$ 项不能为 $b_j$ 。也就是说， 当 $i$ 满足 $l_j\leq i\leq r_j$ 时，$a_i\neq b_j$。

请你输出长度为 $n$ 的满足所有限制条件的好数列个数。答案对 $10^9+7$ 取模。

Input

第一行两个整数 $n,m$，分别表示数列的长度和限制条件个数。 接下来 $m$ 行，每行三个整数 $l_j,r_j,b_j$，表示对于 $l_j\leq i\leq r_j$，$a_i\neq b_j$。

Output

输出一个整数，表示满足所有条件的数列个数对 $10^9+7$ 取模后的结果。

Samples

6 3
2 3 0
4 5 1
3 3 2

4

Constraints

$3\leq n\leq 10^{18}$ $0\leq m\leq 10^4$ $2\leq l_j\leq r_j\leq {n-1}$ $0\leq b_j\leq 2$

Note

样例中满足条件的数列有：$[1,1,1,0,0,1]$、$[1,1,1,2,2,1]$、$[1,2,1,0,0,1]$、$[1,2,1,2,2,1]$。

Resources

2021 UESTC ICPC Training for Dynamic Programming