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 <bits/stdc++.h>
using namespace std;
typedef long long Long;

const Long N = 302;
const Long mod = 1e9 + 7;

vector< pair<Long,Long> > fin[N];
Long n, m;
Long memo[N][N][N];

Long dp(Long p1, Long p2, Long p3){
	if(memo[p1][p2][p3] != -1){
		return memo[p1][p2][p3];
	}
	
	Long mx = max({p1,p2,p3});
	for(Long i = 0; i < (Long)fin[mx].size(); i++){
		Long cnt = 0;
		if(fin[mx][i].first <= p1) cnt++;
		if(fin[mx][i].first <= p2) cnt++;
		if(fin[mx][i].first <= p3) cnt++;
		if(cnt != fin[mx][i].second){
			memo[p1][p2][p3] = 0;
			return 0;
		}
	}
	
	Long pos = mx+1;
	if(pos == n+1){
		return 1;
	}
	
	Long ans = 0;
	ans += dp(pos,p2,p3);
	ans %= mod;
	ans += dp(p1,pos,p3);
	ans %= mod;
	ans += dp(p1,p2,pos);
	ans %= mod;
	memo[p1][p2][p3] = ans;
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout.precision(10);
	cout << fixed;
	
	for(Long i = 0; i < N; i++){
		for(Long j = 0; j < N; j++){
			for(Long k = 0; k < N; k++){
				memo[i][j][k] = -1;
			}
		}
	}
	
	Long l, r, c;
	cin >> n >> m;
	
	for(Long i = 0; i < m; i++){
		cin >> l >> r >> c;
		fin[r].push_back({l,c});
	}
	
	cout << dp(0,0,0) << "\n";
	return 0;
}