CF1558D Top-Notch Insertions

考虑使用插入排序算法对长度为 $n$ 的整数序列 $[a_1, a_2, \ldots, a_n]$ 进行非递减排序。 对于每个 $i$，从 $2$ 到 $n$，执行以下操作。如果 $a_i \ge a_{i-1}$，则什么也不做，继续下一个 $i$。否则，找到最小的 $j$ 使得 $a_i < a_j$，将位置从 $j$ 到 $i-1$ 的元素都向右移动一位，并将 $a_i$ 的初始值写入位置 $j$。在这种情况下，我们称其为将元素从位置 $i$ 插入到位置 $j$。 可以注意到，在处理任意 $i$ 之后，序列的前缀 $[a_1, a_2, \ldots, a_i]$ 都是非递减有序的，因此该算法确实可以对任意序列进行排序。 例如，对 $[4, 5, 3, 1, 3]$ 进行排序的过程如下： - $i = 2$：$a_2 \ge a_1$，不做任何操作； - $i = 3$：$j = 1$，将第 $3$ 个元素插入到第 $1$ 个位置：$[3, 4, 5, 1, 3]$； - $i = 4$：$j = 1$，将第 $4$ 个元素插入到第 $1$ 个位置：$[1, 3, 4, 5, 3]$； - $i = 5$：$j = 3$，将第 $5$ 个元素插入到第 $3$ 个位置：$[1, 3, 3, 4, 5]$。 现在给定一个整数 $n$ 和 $m$ 个整数对 $(x_i, y_i)$。我们关心的是：有多少个长度为 $n$，每个元素都是 $1$ 到 $n$ 之间（可以重复）的整数序列，满足用上述算法排序时，恰好会依次执行 $m$ 次插入操作，分别是从位置 $x_1$ 插入到 $y_1$，然后从 $x_2$ 插入到 $y_2$，……，最后从 $x_m$ 插入到 $y_m$。 请你输出满足条件的序列个数，答案对 $998\,244\,353$ 取模。

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 10^5$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$；$0 \le m < n$），表示序列长度和插入操作次数。 接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$2 \le x_1 < x_2 < \ldots < x_m \le n$；$1 \le y_i < x_i$）。这些行按时间顺序描述插入操作。 保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。注意，$n$ 的总和没有类似的限制。

对于每组测试数据，输出一个整数，表示长度为 $n$、元素取值范围为 $1$ 到 $n$ 的所有满足条件的序列个数，对 $998\,244\,353$ 取模。

在第一个测试用例中，算法没有执行任何插入操作，因此初始序列已经是非递减有序的。这样的序列共有 $10$ 个，分别是 $[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]$。 在第二个测试用例中，唯一满足条件的序列是 $[3, 2, 1]$。 在第三个测试用例中，$[4, 5, 3, 1, 3]$ 是满足条件的序列之一。 由 ChatGPT 4.1 翻译