CF1558D.Top-Notch Insertions

Consider the insertion sort algorithm used to sort an integer sequence $[a_1, a_2, \ldots, a_n]$ of length $n$ in non-decreasing order.

For each $i$ in order from $2$ to $n$, do the following. If $a_i \ge a_{i-1}$, do nothing and move on to the next value of $i$. Otherwise, find the smallest $j$ such that $a_i \lt a_j$, shift the elements on positions from $j$ to $i-1$ by one position to the right, and write down the initial value of $a_i$ to position $j$. In this case we'll say that we performed an insertion of an element from position $i$ to position $j$.

It can be noticed that after processing any $i$, the prefix of the sequence $[a_1, a_2, \ldots, a_i]$ is sorted in non-decreasing order, therefore, the algorithm indeed sorts any sequence.

For example, sorting $[4, 5, 3, 1, 3]$ proceeds as follows:

• $i = 2$: $a_2 \ge a_1$, do nothing;
• $i = 3$: $j = 1$, insert from position $3$ to position $1$: $[3, 4, 5, 1, 3]$;
• $i = 4$: $j = 1$, insert from position $4$ to position $1$: $[1, 3, 4, 5, 3]$;
• $i = 5$: $j = 3$, insert from position $5$ to position $3$: $[1, 3, 3, 4, 5]$.

You are given an integer $n$ and a list of $m$ integer pairs $(x_i, y_i)$. We are interested in sequences such that if you sort them using the above algorithm, exactly $m$ insertions will be performed: first from position $x_1$ to position $y_1$, then from position $x_2$ to position $y_2$, ..., finally, from position $x_m$ to position $y_m$.

How many sequences of length $n$ consisting of (not necessarily distinct) integers between $1$ and $n$, inclusive, satisfy the above condition? Print this number modulo $998\,244\,353$.

考虑使用插入排序算法对长度为 $n$ 的整数序列 $[a_1, a_2, \ldots, a_n]$ 进行非递减排序。

对每个 $i$（按顺序从 $2$ 到 $n$），执行以下操作：若 $a_i \ge a_{i-1}$，则不作任何操作，继续处理下一个 $i$；否则，找出最小的 $j$ 使得 $a_i \lt 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)$ 的列表。我们关注满足如下条件的序列：当使用上述算法对其进行排序时，恰好执行 $m$ 次插入操作，且依次为：从位置 $x_1$ 插入到位置 $y_1$，然后从位置 $x_2$ 插入到位置 $y_2$，……，最后从位置 $x_m$ 插入到位置 $y_m$。

有多少个长度为 $n$ 的序列（其元素为 $1$ 到 $n$ 之间的整数，允许重复）满足上述条件？请输出该数目对 $998\,244\,353$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$; $0 \le m \lt n$) — the length of the sequence and the number of insertions.

The $i$-th of the following $m$ lines contains two integers $x_i$ and $y_i$ ($2 \le x_1 \lt x_2 \lt \ldots \lt x_m \le n$; $1 \le y_i \lt x_i$). These lines describe the sequence of insertions in chronological order.

It is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$. Note that there is no constraint on the sum of $n$ of the same kind.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$；$0 \le m \lt n$）——分别表示序列的长度和插入操作的次数。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$2 \le x_1 \lt x_2 \lt \ldots \lt x_m \le n$；$1 \le y_i \lt x_i$）。这些行按时间顺序描述插入操作序列。

保证所有测试用例的 $m$ 值之和不超过 $2 \cdot 10^5$。注意：对所有测试用例的 $n$ 值之和并无类似限制。

For each test case, print the number of sequences of length $n$ consisting of integers from $1$ to $n$ such that sorting them with the described algorithm produces the given sequence of insertions, modulo $998\,244\,353$.

对于每个测试用例，输出长度为 $n$、由 $1$ 到 $n$ 的整数构成的序列的个数（模 $998\,244\,353$），使得使用所描述的算法对其进行排序时，恰好产生给定的插入序列。

In the first test case, the algorithm performs no insertions — therefore, the initial sequence is already sorted in non-decreasing order. There are $10$ such sequences: $[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]$.

In the second test case, the only sequence satisfying the conditions is $[3, 2, 1]$.

In the third test case, $[4, 5, 3, 1, 3]$ is one of the sought sequences.

在第一个测试用例中，该算法不执行任何插入操作——因此，初始序列本身已按非递减顺序排好序。满足条件的序列共有 $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]$ 是所求序列之一。