F. Bubble Sorttime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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 roundsAs 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). InputEach 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$$$. OutputFor each test case, output a single integer — the number of possible permutations, modulo $$$998\,244\,353$$$.ExampleInput64 30 1 11 3 32 4 43 20 3 31 2 34 31 2 22 3 40 1 25 31 1 43 5 54 5 510 51 2 32 3 43 4 54 5 65 6 71000000 0Output21880192600373341033NoteIn 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]$$$.