CF2146F Bubble Sort
Description
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).
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 Format
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 Format
For each test case, output a single integer — the number of possible permutations, modulo $ 998\,244\,353 $ .
Explanation/Hint
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] $ .