Problem: 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^9+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 M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M


Output

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

Examples

Input

3 1
1 3 3


Output

6


Input

4 2
1 3 1
2 4 2


Output

6


Input

1 3
1 1 1
1 1 2
1 1 3


Output

0


Input

8 10
2 6 2
5 5 1
3 5 2
4 7 3
4 4 1
2 3 1
7 7 1
1 5 2
1 7 3
3 4 2


Output

108

Solution (in CPP):

Solution:
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=305,mo=1e9+7;
int n,m,i,j,k,mn[N][3],mx[N][3],f[N][N],ans;
int read(){
	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;
}
void add(int &x,int k){x=(x+k)%mo;}
int main(){
	for (n=read(),m=read(),i=1;i<=n;i++)
		for (j=0;j<3;j++) mn[i][j]=n;
	for (;m--;){
		int y=read(),x=read(),k=read()-1;
		mn[x][k]=min(mn[x][k],y);
		mx[x][k]=max(mx[x][k],y);
	}
	for (f[0][0]=1,i=0;i<=n;i++)
		for (j=i;~j;j--) for (k=j;~k;k--) if (f[j][k]){
			int v=f[j][k];f[j][k]=0;
			if (mx[i][0]&&mn[i][0]<=j) continue;
			if (mx[i][1]&&(mx[i][1]>j||mn[i][1]<=k)) continue;
			if (mn[i][2]&&mx[i][2]>k) continue;
			if (i==n){add(ans,v);continue;}
			add(f[j][k],v);add(f[i][j],v);add(f[i][k],v);
		}
	printf("%d",ans);
}