最初,我们有一个数组,它是大小 $$$n$$$ 的排列(大小为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次)。
我们执行了 $$$q$$$ 操作。在第 $$$i$$$ 操作期间,我们执行了以下操作:
- 选择我们拥有至少 $$$2$$$ 元素的任何数组;
- 将其分成两个非空数组(前缀和后缀);
- 写入两个整数$$$l_i$$$和$$$r_i$$$,其中$$$l_i$$$是分割后左边部分的最大元素,$$$r_i$$$是右边部分的最大元素;
- 从我们可以使用的数组池中删除我们选择的数组,并将两个结果部分添加到池中。
例如,假设初始数组为$$$[6, 3, 4, 1, 2, 5]$$$,我们执行以下操作:
1. 选择数组 $$$[6, 3, 4, 1, 2, 5]$$$ 并将其拆分为 $$$[6, 3]$$$ 和 $$$[4, 1, 2, 5]$$$。然后我们写$$$l_1 = 6$$$和$$$r_1 = 5$$$,我们得到的数组是$$$[6, 3]$$$和$$$[4, 1, 2, 5]$$$;
2. 选择数组 $$$[4, 1, 2, 5]$$$ 并将其拆分为 $$$[4, 1, 2]$$$ 和 $$$[5]$$$。然后我们写$$$l_2 = 4$$$和$$$r_2 = 5$$$,我们得到的数组是$$$[6, 3]$$$,$$$[4, 1, 2]$$$和$$$[5]$$$;
3. 选择数组 $$$[4, 1, 2]$$$ 并将其拆分为 $$$[4]$$$ 和 $$$[1, 2]$$$。然后我们写$$$l_3 = 4$$$和$$$r_3 = 2$$$,我们得到的数组是$$$[6, 3]$$$,$$$[4]$$$,$$$[1, 2]$$$和$$$[5]$$$。
给定两个整数 $$$n$$$ 和 $$$q$$$,以及两个序列 $$$[l_1, l_2, \dots, l_q]$$$ 和 $$$[r_1, r_2, \dots, r_q]$$$。如果我们可以执行 $$$q$$$ 操作并生成给定的序列 $$$[l_1, l_2, \dots, l_q]$$$ 和 $$$[r_1, r_2, \dots, r_q]$$$,则大小 $$$n$$$ 的排列被称为有效。
计算有效排列的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le q < n \le 3 \cdot 10^5$$$)。
第二行包含 $$$q$$$ 整数 $$$l_1, l_2, \dots, l_q$$$ ($$$1 \le l_i \le n$$$)。
第三行包含 $$$q$$$ 整数 $$$r_1, r_2, \dots, r_q$$$ ($$$1 \le r_i \le n$$$)。
对输入的附加约束:至少存在一种排列可以产生给定序列 $$$[l_1, l_2, \dots, l_q]$$$ 和 $$$[r_1, r_2, \dots, r_q]$$$。
输出
打印一个整数 — 有效排列的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
6 3 6 4 4 5 5 2
输出 #1
30
输入 #2
10 1 10 9
输出 #2
1814400
输入 #3
4 1 2 4
输出 #3
8