CF2124F2.Appending Permutations (Hard Version)

这是该问题的困难版本。不同之处在于本版本中 $n \leq 5000$。只有在你解决了所有版本的问题后，才能进行 hack。

你有一个初始为空的数组 $a$。你可以进行如下操作任意次：

• 选择一个整数 $s \ge 1$，并将数组 $[1, 2, \ldots, s]$ 的一个循环移位结果追加到 $a$ 的末尾。具体来说，选择整数 $s$ 和 $r$，满足 $1 \le r \le s$，然后将数组

  $$[r, r+1, \ldots, s, 1, 2, \ldots, r-1]$$

  追加到 $a$ 的末尾。

你还给定一个整数 $n$ 和 $m$ 个限制条件，每个限制条件形如 $a_i \ne x$。也就是说，对于每个限制条件，最终数组的第 $i$ 个位置的值不能等于 $x$。

你的任务是统计，使用上述操作可以构造出多少个长度恰好为 $n$ 且满足所有限制条件的不同数组。只要在 $1$ 到 $n$ 的某个位置不同，就认为两个数组不同。

请输出答案对 $998\,244\,353$ 取模后的结果。

每个测试点包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 5000$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 5000, 0 \leq m \leq \min(5000, n^2)$），分别表示数组 $a$ 的长度和限制条件的数量。

接下来的 $m$ 行，每行包含两个整数 $i$ 和 $x$（$1 \leq i,x \leq n$），表示最终数组的第 $i$ 个位置不能等于 $x$。保证没有重复的限制条件。

保证所有测试用例中 $n$ 的总和不超过 $5000$，$m$ 的总和也不超过 $5000$。

对于每个测试用例，输出一个整数，表示满足条件的数组数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，总共有 $7$ 个可达数组：$[1,2,3], [2,3,1], [3,1,2], [1,1,2], [1,2,1], [2,1,1], [1,1,1]$。

在第二个测试用例中，上述 $7$ 个数组都不合法，因为所有元素都不能为 $1$，而所有数组中至少有一个 $1$。

在第三个测试用例中，只有 $[2,3,1]$ 被计入。

由 ChatGPT 4.1 翻译