CF2124F2 Appending Permutations (Hard Version)

**This is the hard version of the problem. The difference between the versions is that in this version, $n \leq 5000$. You can hack only if you solved all versions of this problem.** You are given an initially empty array $a$. You may perform the following operation any number of times: - Choose an integer $s \ge 1$ and append a cyclic shift of the array $[1, 2, \ldots, s]$ to the end of $a$. Formally, select integers $s$ and $r$ such that $1 \le r \le s$, and append the array $$ [r, r+1, \ldots, s, 1, 2, \ldots, r-1] $$ to the end of $a$. You are also given an integer $n$ and $m$ restrictions of the form $a_i \ne x$. That is, for each of the $m$ restrictions, the value at position $i$ in the final array must not be equal to $x$. Your task is to count the number of distinct arrays of length exactly $n$ that can be constructed using the allowed operation and satisfy all of the given restrictions. Two arrays are considered different if they differ at any position from $1$ to $n$. Print the answer modulo $998\,244\,353$.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \leq n \leq 5000, 0 \leq m \leq \min(5000, n^2) $ ) — the length of the array $ a $ and the number of restrictions. The following $ m $ lines each contain two integers $ i $ and $ x $ ( $ 1 \leq i,x \leq n $ ), indicating that $ a_i\neq x $ is a requirement of the final array. It is guaranteed that no limitation is given more than once. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ , and the sum of $ m $ over all test cases does not exceed $ 5000 $ .

For each test case, output the number of arrays modulo $ 998\,244\,353 $ .

In the first test case, there are $ 7 $ total attainable arrays: $ [1,2,3], [2,3,1], [3,1,2], [1,1,2], [1,2,1], [2,1,1], [1,1,1] $ . In the second test case, none of the above $ 7 $ are valid because no element is allowed to be $ 1 $ , and all of the arrays have at least one $ 1 $ . In the third case, only $ [2,3,1] $ is counted.