题目背景

小 F 喜欢字符串。

小 S 喜欢后缀数组。

有 $n$ 只鼠，它们被绳子依次串起来，顺次排成一排。每只鼠有一个体型大小 $a_i$。小 F 定义一个后缀为从某一只鼠开始，到最后一只鼠构成的序列。

对于两个鼠的序列 $\sigma, \pi$，我们称 $\sigma < \pi$ 当且仅当存在一个位置 $i$，满足 $\sigma$ 和 $\pi$ 中前 $i - 1$ 只鼠的体型大小对应相同，且 $\sigma$ 的第 $i$ 只鼠不存在或者比 $\pi$ 的第 $i$ 只鼠小。

小 S 给予了这些鼠一个排列 $\boldsymbol p = \left[ p_1, p_2, \ldots, p_n \right]$，满足对于 $\forall i < j$，从第 $i$ 只鼠开始的后缀小于从第 $j$ 只鼠开始的后缀。

小 F 观察了这一列鼠后，发现它们中有非常多的鼠具有相同的体型大小。于是，她问小 S：这列鼠有多少种不同的大小呢？

鼠在不停地挣扎，想要挣脱绳子的束缚。小 S 还没有看清这些鼠的大小，鼠便把绳子都咬断了，开始四处乱窜。

小 S 有些气恼，但是她还是想要知道答案。她带着已经得到的排列问小 F：对于所有满足 “给予它的排列为 $\boldsymbol p$ 的” 鼠的序列，答案 (鼠的大小的种类数) 的最小值可以是多少？

鼠在不停地挣扎，想要逃离这阴暗的房间。小 S 还没有计算出来，鼠便把小 S 得到的排列中的若干数字也咬掉了，带着碎片纷纷逃离房间。

小 S 有些气恼，但是她还是想要知道答案。她带着那残缺的排列问小 F：对于剩下的数的所有 $k!$ 种排列方案 ($k$ 为被鼠咬掉的数的数量)，答案 (鼠的大小的种类数的最小值) 的总和是多少？

小 S 哭了。

题目描述

本题包含三个问题：

• 问题 0：给定一个长度为 $n$ 的序列以及它的后缀数组 $\boldsymbol p$，求这个序列中有多少个不同的数。
• 问题 1：给定一个长度为 $n$ 的排列 $\boldsymbol p$，对于所有满足后缀数组为 $\boldsymbol p$ 的长度为 $n$ 的序列，求不同的数的数量的最小值。
• 问题 2：给定一个长度为 $n$ 的残缺的排列 $\tilde {\boldsymbol p}$ (有 $k$ 个位置未知)，对于所有 $k!$ 种完整的排列，求问题 1 的答案之和。

在不同的测试点中，你将可能需要回答不同的问题。我们将用 $\mathrm{op}$ 来指代你需要回答的问题编号 (对应上述 $0, 1, 2$)。

在问题 2 中，由于答案可能很大，因此你只需要输出答案对 $998244353$ 取模的结果即可。

输入格式

第一行包含两个非负整数 $n, \mathrm{op}$，分别表示鼠的数量和子问题的类型。

如果 $\mathrm{op} = 0$，则第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每只鼠的体型大小；第三行包含 $n$ 个正整数 $p_1, p_2, \cdots, p_n$，表示小 S 得到的排列。

如果 $\mathrm{op} = 1$，则第二行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$，表示小 S 得到的排列。

如果 $\mathrm{op} = 2$，则第二行包含 $n$ 个非负整数 $\tilde p_1, \tilde p_2, \ldots, \tilde p_n$，表示小 S 的残缺的排列。$\tilde p_i = 0$ 表示这一个值被鼠 "咬掉" 的，否则 $\tilde p_i$ 表示排列中第 $i$ 位的值。

每行中的两个整数之间均用一个空格隔开，鼠的编号是从 $1$ 开始的。

输出格式

输出一行一个整数，表示对应问题的答案对 $998244353$ 取模的结果。

样例 1

3 0
10 20 30
1 2 3

3

共有 $3$ 只鼠，它们的体型大小分别为 $10, 20, 30$，排列为 $1, 2, 3$。容易看出，这列鼠一共有 $3$ 种不同的大小。

3 1
1 2 3

2

如果 $3$ 只鼠的体型大小为 $10, 10, 20$，则小 S 得到的排列也应为 $1, 2, 3$。而此时，这列鼠只有 $2$ 种不同的大小：$10$ 和 $20$。

反之，如果这列鼠只有 $1$ 种大小，即这 $3$ 只鼠的大小相同，则小 S 得到的排列必定为 $3, 2, 1$，矛盾。这也说明 $2$ 的确是最小的答案。

3 2
0 0 3

5

若排列为 $1, 2, 3$，如样例二所述，最少有 $2$ 种不同的大小。

若排列为 $2, 1, 3$，则鼠的体型大小可以为 $20, 10, 30$，此时共有 $3$ 种不同的大小。

仿照样例二，可以证明此时鼠的大小的种类数不得小于 $3$。

故答案为 $2 + 3 = 5$。

样例 4

见附加文件中的 ex_suffix4.in 与 ex_suffix4.out。

该组样例满足 $\mathrm{op} = 0$。

样例 5

见附加文件中的 ex_suffix5.in 与 ex_suffix5.out。

该组样例满足 $\mathrm{op} = 1$。

样例 6

见附加文件中的 ex_suffix6.in 与 ex_suffix6.out。

该组样例满足 $\mathrm{op} = 2$。

数据范围与提示

对于所有的测试点，均满足 $1 \leq n \leq 5 \times 10^5; 1 \leq a_i \leq 10^9; 1 \leq p_i \leq n; 0 \leq \tilde p_i \leq n$，当 $\mathrm{op} = 2$ 时存在至少一个 $i$ 使得 $\tilde p_i = 0$。

问题类型 ($\mathrm{op} =$)	测试点编号	$n$	其它性质
0	1	$\leq 10$	无
	2	$\leq 5 \times 10^5$
	3
1	4	$= 3$
	5	$= 5$
	6	$\leq 10$
	7	$\leq 500$
	8	$\leq 5000$
	9
	10	$\leq 50000$
	11
	12	$\leq 5 \times 10^5$	$p_i = i$
	13		无
	14
2	15	$= 3$
	16	$= 5$
	17	$\leq 10$
	18	$\leq 500$	满足 $\tilde p_i = 0$ 的 $i$ 不超过 $5$ 个
	19	$\leq 5000$	无
	20		满足 $\tilde p_i = 0$ 的 $i$ 不超过 $5$ 个
	21	$\leq 50000$	无
	22		所有 $\tilde p_i = 0$
	23	$\leq 5 \times 10^5$	存在整数 $t$ ($1 \leq t < n$)，满足 $\tilde p_i = \begin{cases} i & i \leq t \\ 0 & i > t \end{cases}$
	24		存在整数 $t$ ($1 \leq t < n$)，满足 $\tilde p_i = 0$ 当且仅当 $i > t$
	25		无