E. Bârlad
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Bârlad is the home of some rocky landscapes and very bad drivers. The train passed Bârlad way too fast for Little IR12660 to actually visit it. So now he can only imagine what Bârlad might look like. He knows Bârlad is a city stretching along a single line, and he also knows that if the landscape across this line gets too complicated for the locals, they might crash. So, he formulates the following problem:

Count the number of permutations of order $$$N$$$ that satisfy $$$M$$$ restrictions of the following types:

  • The subarray from $$$l$$$ to $$$r$$$ is a valley.
  • The subarray from $$$l$$$ to $$$r$$$ is a mountain.

An array is considered:

  • A valley if it strictly decreases to a minimum point and then strictly increases. For example, $$$[5, 3, 1, 4, 6]$$$ is a valley.
  • A mountain if it strictly increases to a maximum point and then strictly decreases. For example, $$$[1, 3, 5, 4, 2]$$$ is a mountain.

A strictly increasing or strictly decreasing array is considered neither a valley nor a mountain.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq T \leq 500$$$) — the number of test cases.

The description of each test case is as follows:

  • The first line of each test case contains two integers $$$N$$$ ($$$3 \le N \le 2\,000$$$) and $$$M$$$ ($$$0 \leq M \leq 2\,000$$$) — the size of the permutation and the number of restrictions.
  • The next $$$M$$$ lines each contain three integers $$$l$$$, $$$r$$$, and $$$type$$$ ($$$1 \leq l, l + 1 \lt r\leq N$$$, $$$1 \leq type \leq 2$$$):
    • $$$l$$$ and $$$r$$$ specify the range of the subarray.
    • $$$type = 1$$$ means the subarray must be a valley.
    • $$$type = 2$$$ means the subarray must be a mountain.

It is guaranteed that the sum of $$$N$$$ across all test cases does not exceed $$$2\,000$$$ and the sum of $$$M$$$ across all test cases does not exceed $$$2\,000$$$.

Output

For each test case, output a single integer — the number of permutations of size $$$n$$$ that satisfy all $$$m$$$ restrictions modulo $$$10^9 + 7$$$.

Example
Input
5
5 2
1 3 1
2 5 2
4 1
1 4 1
6 3
1 4 2
2 5 1
3 6 2
3 2
1 3 1
1 3 2
5 0
Output
20
6
0
0
120