Problem Statement

There are N squares arranged in a row. The squares are numbered 1, 2, …, N, from left to right.

Snuke is painting each square in red, green or blue. According to his aesthetic sense, the following M conditions must all be satisfied. The i-th condition is:

• There are exactly x_i different colors among squares l_i, l_i+1, …, r_i.

In how many ways can the squares be painted to satisfy all the conditions? Find the count modulo 10⁹+7.

Constraints

• 1≤N≤300
• 1≤M≤300
• 1≤l_i≤r_i≤N
• 1≤x_i≤3

Input

Input is given from Standard Input in the following format:

N Ml1 r1 x1l2 r2 x2:lM rM xM

Output

Print the number of ways to paint the squares to satisfy all the conditions, modulo 10⁹+7.

Sample Input 1

3 11 3 3

Sample Output 1

6

The six ways are:

• RGB
• RBG
• GRB
• GBR
• BRG
• BGR

where R, G and B correspond to red, green and blue squares, respectively.

Sample Input 2

4 21 3 12 4 2

Sample Output 2

6

The six ways are:

• RRRG
• RRRB
• GGGR
• GGGB
• BBBR
• BBBG

Sample Input 3

1 31 1 11 1 21 1 3

Sample Output 3

0

There are zero ways.

Sample Input 4

8 102 6 25 5 13 5 24 7 34 4 12 3 17 7 11 5 21 7 33 4 2

Sample Output 4

108     还是小清新dp比较好，写起代码来非常的令人身心愉悦233333     让我们设 f[j][k][u] 为最近出现三种颜色的位置为j,k,u的方案数，那么转移直接把随便一维变成当前枚举的i即可。     至于限制条件，我们只需要在i==r的时候把 (j>=l) + (k>=l) + (u>=l) != x 的 f[j][k][u] 设置成0即可。     看起来是O(N^4)的？？？ 实际上因为至少一维要是i-1或者i，所以复杂度实际上是O(N^3)的。

#include
      
       #include
       
        #define ll long longusing namespace std;#define pb push_backconst int ha=1e9+7,maxn=305;inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}int f[maxn][maxn][maxn],n,m,k,L,R,ans;vector
        
          g[maxn][4];inline void update(int p){	for(int i=1;i<=3;i++)	    for(int j=g[p][i].size()-1,l;j>=0;j--){	    	l=g[p][i][j];	    		    	for(int a=0;a<=p;a++)	    	    for(int b=0;b<=p;b++)	    	        for(int c=(a
         
          
           <=p;c++)	    	            if((a>=l)+(b>=l)+(c>=l)!=i) f[a][b][c]=0;		}}inline void dp(){	f[0][0][0]=1;	for(int i=1;i<=n;i++){		for(int j=0;j