F. Bubble Sort
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You have just learned the algorithm bubble sort, which is able to sort an array in non-descending order. Let's define the function $$$\text{sort}(a)$$$ as in the following pseudocode:

function sort(array a):
    rounds := 0
    n := length of a
    while a is not non-decreasing:
        rounds := rounds + 1
        for i from 1 to n - 1:
            if a[i] > a[i + 1]:
                swap(a[i], a[i + 1])
    return rounds

As it is shown, the return value of $$$\text{sort}(a)$$$ represents the number of rounds needed to make array $$$a$$$ sorted in non-descending order by using bubble sort.

You are given an integer $$$n$$$, as well as $$$m$$$ integer tuples $$$(k_i,l_i,r_i)$$$ ($$$1\le i\le m$$$). Count the number of permutations$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$, modulo $$$998\,244\,353$$$, so that the following restrictions are satisfied:

  • For each $$$1\le i\le n$$$, let $$$b_i=\text{sort}([p_1,p_2,\ldots,p_{i}])$$$, then
  • For each $$$1\le j\le m$$$, let $$$x$$$ be the number of indices $$$y$$$ ($$$1\le y\le n$$$) such that $$$b_y\le k_j$$$, then $$$l_j\le x\le r_j$$$ holds.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n\leq 10^6$$$, $$$0\leq m\leq 1000$$$).

Then $$$m$$$ lines follow, the $$$i$$$-th line containing three integers $$$k_i$$$, $$$l_i$$$, and $$$r_i$$$ ($$$0\le k_i\le n - 1$$$, $$$1\le l_i\le r_i\le n$$$) — the restrictions.

It is guaranteed that the sum of $$$m^2$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the number of possible permutations, modulo $$$998\,244\,353$$$.

Example
Input
6
4 3
0 1 1
1 3 3
2 4 4
3 2
0 3 3
1 2 3
4 3
1 2 2
2 3 4
0 1 2
5 3
1 1 4
3 5 5
4 5 5
10 5
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
1000000 0
Output
2
1
8
80
192600
373341033
Note

In the first test case, only permutations $$$[3,1,4,2]$$$ and $$$[4,1,3,2]$$$ satisfy the restrictions. Take $$$[3,1,4,2]$$$ as an example. Let's calculate the array $$$b$$$:

  • $$$\text{sort}([3])=0$$$;
  • $$$\text{sort}([3,1])=1$$$;
  • $$$\text{sort}([3,1,4])=1$$$;
  • $$$\text{sort}([3,1,4,2])=2$$$.

Thus, $$$b=[0,1,1,2]$$$. It is easy to show that it satisfies all the restrictions.

In the second test case, only permutation $$$[1,2,3]$$$ satisfies the restrictions.

In the third test case, the following $$$8$$$ permutations satisfy the restrictions:

  • $$$[2,3,1,4]$$$;
  • $$$[2,4,1,3]$$$;
  • $$$[3,2,1,4]$$$;
  • $$$[3,4,1,2]$$$;
  • $$$[3,4,2,1]$$$;
  • $$$[4,2,1,3]$$$;
  • $$$[4,3,1,2]$$$;
  • $$$[4,3,2,1]$$$.