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 PYTHON3):

Solution:
import sys
readline = sys.stdin.readline

def viol(c2, c3, l, x):
    res = False
    if x == 1:
        if not c2 < l:
            res = True
    elif x == 2:
        if not c3 < l <= c2:
            res = True
    else:
        if not l <= c3:
            res = True
    return res
MOD = 10**9+7
N, M = map(int, readline().split())
limit = [[] for _ in range(N+3)]

for _ in range(M):
    l, r, x = map(int, readline().split())
    limit[r+2].append((l+2, x))

dp = [[0, 0], [1, 0]]

for i in range(2, N+2):    
    dp2 = [[0]*(i+1) for _ in range(i+1)]
    r = i
    for g in range(r):
        for b in range(g):
            d = dp[g][b]
            dp2[g][b] = (dp2[g][b] + d)%MOD
            dp2[r][b] = (dp2[r][b] + d)%MOD
            dp2[r][g] = (dp2[r][g] + d)%MOD
    for l, x in limit[i+1]:
        r = i+1
        for g in range(r):
            for b in range(g):
                if viol(g, b, l, x):
                    dp2[g][b] = 0
    dp = [d[:] for d in dp2]
    
res = 0
for g in range(N+2):
    for b in range(g):
        res = (res + dp[g][b]) % MOD
print(res)