Description

Little Y has recently become obsessed with a tower defense game.

Today, she focuses on a character, Little W. Little W can block at most 2 enemies at the same time and perform several attacks. Each attack can be one of two types:

1. Normal attack: Deals 1 damage to all blocked enemies simultaneously.
2. Critical strike: Deals 2 damage to all blocked enemies simultaneously.

Now, Little Y gives Little W $T$ tasks. In each task, Little W needs to attack exactly $n$ times to defeat $m$ enemies. The $i$-th enemy has health $k_i$ and must be defeated within the $l_i$-th to $r_i$-th attacks. Little Y will not make it too hard: Little W never needs to face 3 or more enemies at once.

Little Y wants to know: how many valid attack sequences satisfy all requirements? Since the answer can be huge, you only need to output it modulo $10^9+7$.

Two attack sequences are different if there exists an $i \in [1,n]$ such that one sequence uses a normal attack on the $i$-th step and the other uses a critical strike.

Formal Statement

Given positive integers $n$ and $m$ triples $(l, r, k)$, a sequence is called good if and only if:

1. All elements are in $\{1,2\}$.
2. For every $i \in [1,m]$, $\sum\limits_{j=l_i}^{r_i} a_j = k_i$.

You need to find the number of good sequences modulo $10^9+7$.

Guarantee: Every position is covered by at most 2 intervals, i.e.

$$\forall i\in[1,n],\; \sum\limits_{j=1}^m \left[\,i\in[l_j,r_j]\,\right] \le 2$$

There are $T$ test cases in one test point.

Input Format

The first line contains an integer $T$, the number of tasks.

For each test case:

• The first line contains two integers $n, m$.
• The next $m$ lines each contain three integers $l, r, k$, representing the information of an enemy.

Output Format

Output $T$ lines. Each line contains one integer: the answer for the $i$-th test case modulo $10^9+7$.

3
5 2
1 4 7
2 5 7
10 3
3 3 1
3 4 2
7 9 4
5000 6
1657 2689 1560
2 1789 2643
1790 3701 2878
1360 1655 429
2692 3856 1744
3 1357 2010

4
96
952912621

Hint

Data Constraints

Test Case	$n \le$	$m \le$	Special Property
$1\sim 2$	$16$	$32$	None
$3\sim 5$	$36$	$72$
$6\sim 7$	$6000$	$6000$	Yes
$8\sim 9$		$2$	None
$10\sim 12$	$200$	$400$
$13\sim 15$	$300$	$600$
$16\sim 19$	$3000$	$6000$
$20\sim 25$	$8000$	$16000$

Special Property: Every position is covered by at most 1 interval: $\forall i\in[1,n],\; \sum\limits_{j=1}^m \left[\,i\in[l_j,r_j]\,\right] \le 1$.

For $100\%$ data: $1\le n\le 8000,\ 1\le m\le 2n,\ 1\le T\le 10$.

Hard Guarantee: $\forall i\in[1,n],\; \sum\limits_{j=1}^m \left[\,i\in[l_j,r_j]\,\right] \le 2$.