题目描述

123型序列 是指一个仅由 1,2,3 三个数字组成的序列。

有一个长度为$n$的 123型序列 ，且已知$m$个限制条件，每个限制条件包含$3$个整数$[l,r,cnt]$表示在序列第$l$个到第$r$个数字内，共出现了$cnt$个不同的数字。

请你求出，有多少个长度为$n$的 123型序列 满足给定限制条件？由于答案过大，请对$10^9+7$取模。

输入格式

输入第一行，两个正整数$n,m$ 接下来$m$行，每行$3$个正整数$l,r,cnt$

输出格式

输出满足条件的方案数

4 2
2 4 1
1 3 2

6

样例解释 1

共6种：1222，1333，2111，2333，3111，3222。

数据范围

对于$30\%$的数据，$1\leq n,m \leq 10$ 对于$60\%$的数据，$1\leq n,m \leq 50$ 对于$100\%$的数据，$1\leq n,m \leq 300$ $1 \leq l \lt r \leq n ,1 \leq cnt \leq 3$