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^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$.