分数: 900 点
问题陈述
有一棵有根的树 N 顶点编号自 1 to N。 根是顶点 1,以及顶点的父级 i (2 \leq i \leq N) 是顶点 P_i (P_i<i).
还有长度为整数的序列 M: A=(A_1,A_2,\cdots,A_M) 和 B=(B_1,B_2,\cdots,B_M),由之间的整数组成 1 和 N,包括在内。
A 据说是 好 当且仅当对于每个 i,顶点 A_i 是顶点的祖先 B_i or A_i=B_i。 最初, A 很好。
考虑以下操作 A.
- 选择一个整数 i (1 \leq i \leq M-1)并交换值 A_i 和 A_{i+1}。 在这里, A 手术后必须保持良好状态。
求模数 998244353,执行此操作可能产生的序列 A 零次或多次。
约束
- 2 \leq N \leq 250000
- 2 \leq M \leq 250000
- 1 \leq P_i <i
- 1 \leq A_i \leq B_i \leq N
- 顶点 对于所有整数, A_i 是顶点的祖先 B_i or A_i=B_i.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M P_2 P_3 \cdots P_N A_1 A_2 \cdots A_M B_1 B_2 \cdots B_M
输出
打印答案。
样本输入 1
3 3 1 2 1 2 1 1 2 3
示例输出 1
2
考虑选择 i=1.The A=(2,1,1) 操作后效果不好,所以本次操作无效。
考虑选择 i=2.The A=(1,1,2) 操作好后,所以本次操作有效。
执行零个或多个操作可能会产生两个序列 A: A=(1,2,1) 和 (1,1,2).
示例输入 2
4 3 1 1 1 2 3 4 2 3 4
示例输出 2
1
示例输入 3
8 13 1 2 2 3 4 4 3 5 3 2 5 4 6 2 8 2 6 7 4 7 5 5 8 5 6 6 5 8 3 6 7 4 7
示例输出 3
8
示例输入 4
30 27 1 2 1 1 5 1 7 1 5 10 1 12 12 13 15 16 12 18 19 18 21 21 23 13 18 18 27 27 13 1 18 1 5 11 12 1 1 1 12 1 12 1 15 1 1 21 1 12 10 2 8 3 1 1 30 12 14 27 30 5 11 17 1 18 24 27 29 27 19 15 28 5 21 21 29 11 2 8 3 4 10 30 22
示例输出 4
60