考虑用于以非递减顺序对长度为 $$$n$$$ 的整数序列 $$$[a_1, a_2, \ldots, a_n]$$$ 进行排序的插入排序算法。
对于从 $$$2$$$ 到 $$$n$$$ 的每个 $$$i$$$,执行以下操作。如果 $$$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)$$$。我们对序列感兴趣,如果使用上述算法对它们进行排序,将执行精确的 $$$m$$$ 插入:首先从位置 $$$x_1$$$ 到位置 $$$y_1$$$,然后从位置 $$$x_2$$$ 到位置 $$$y_2$$$,...,最后,从位置 $$$x_m$$$ 到位置 $$$y_m$$$。
有多少个长度为 $$$n$$$ 且由 $$$1$$$ 和 $$$n$$$(含)之间的整数(不一定不同)组成的序列满足上述条件?打印此数字对 $$$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$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$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$$$ 为模。
示例
输入 #1
3 3 0 3 2 2 1 3 1 5 3 3 1 4 1 5 3
输出 #1
10 1 21
注意
在第一个测试用例中,算法不执行插入 - 因此,初始序列已经按非降序排序。有$$$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]$$$ 是所寻找的序列之一。