Problem 4448: Little Square

After winning every chess tournament on a 100 km radius around Râmnicu-Vâlcea, Bogdan realized his only real opponent is himself. He decided to quit chess and invent his own wooden piece-placing game. He starts with a square board of side $N$ and $N$ L-shaped pieces. The two "arms" of the piece are of equal length, and all pieces have different lengths between $1$ and $N$ .
The rows of the board, as well as its columns, are numbered from $1$ to $N$ . A position on the board is identified by two numbers $X$ and $Y$ , representing the row and the column of that position, respectively. The top left corner of the board is denoted $(1, 1)$ .

\text{Example of a filled board of size 6. Notice the L-shaped pieces.}.

Bogdan wants to find out how many different ways he can arrange the pieces on the board. To make the problem more interesting he decided to impose $P$ restrictions. A restriction consists of 3 integers $(L, X, Y)$ , meaning that the corner of the piece with side length $L$ must be placed in the position $(X,Y)$ . Notice that the piece can be in any orientation as long as its corner is in the correct position.

Task

Given the size $N$ of a board and $P$ restrictions, find how many ways you can complete the board, modulo $10^9 + 7$ , satisfying the $P$ restrictions.

Input data

The first line of the input contains the integer $T$ , the number of games you'll play. \
Each game is given in the following way:

the first line contains the integer $N$ , the length of the board's side;
the second line contains the integer $P$ , the number of imposed restrictions;
the next $P$ lines contain each $3$ integers $L, X, Y$ , with the meaning specified in the statement.

Output data

The output will consist of $T$ lines, the $i$ -th line ( $1 \leq i \leq T$ ) containing the result for the $i$ -th game.

Constraints and clarifications

$1 \leq T \leq 1000$
$1 \leq N \leq 200 \ 000$
$0 \leq P \leq min(100 \ 000,N)$
$1 \leq L, X, Y \leq N$
A piece of any given size will have at most one restriction during a game.
It is guaranteed that there exists at least one way to complete the board.
The sum of $P$ over all test cases doesn't exceed $100 \ 000$ .

#	Score	Constraints
0	0	Examples
1	6	$P = 0$
2	9	$N \leq 8$
3	16	$P = 1, L = 1, X = 1$ (one restriction imposed, for a piece with the side of length $1$ placed at the top of the board)
4	23	$P = 1, L = 1$ (one restriction imposed, for a piece with side length $1$ )
5	17	$P = 1$
6	29	No further restrictions.

Example 1

stdin

stdout

2
4
4

Explanation

For the first game there are 2 ways to fill the board:

\text{The 2 possible ways to complete the 1st game.}.

The second game doesn't have any restrictions, there are 4 ways to complete it.

The third game can be completed in 4 ways:

\text{The 4 possible ways to complete the 3rd game. \\ Note the different orientations of the piece of side length 2.}.

Example 2