← 返回题目列表

Codeforces · 1976/E

E. 可拆分排列

中文机器翻译题面 查看原题

最初,我们有一个数组,它是大小 $$$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