题目描述

有一棵包含编号为 $1$ 到 $N$ 的 $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$ 是 good 的，当且仅当对每个 $i$，顶点 $A_i$ 是顶点 $B_i$ 的祖先，或者 $A_i = B_i$。

初始时，序列 $A$ 是 good 的。

我们考虑对序列 $A$ 进行以下操作：

• 选择一个整数 $i$ ($1 \leq i \leq M-1$)，交换 $A_i$ 和 $A_{i+1}$ 的值。操作后，序列 $A$ 仍必须是 good 的。

请计算，经过 $0$ 次或多次操作后，可能得到的不同序列的个数，并输出该结果对 $998244353$ 取模的值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$P_2$ $P_3$ $\cdots$ $P_N$
$A_1$ $A_2$ $\cdots$ $A_M$
$B_1$ $B_2$ $\cdots$ $B_M$

输出格式

输出可能得到的不同序列的个数，对 $998244353$ 取模。

样例 1

输入

3 3
1 2
1 2 1
1 2 3

输出

2

样例 2

输入

4 3
1 1 1
2 3 4
2 3 4

输出

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

输出

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

输出

60

说明/提示

• $2 \leq N \leq 250000$
• $2 \leq M \leq 250000$
• $1 \leq P_i < i$
• $1 \leq A_i \leq B_i \leq N$
• 对于每个 $i$，顶点 $A_i$ 是顶点 $B_i$ 的祖先，或者 $A_i = B_i$

样例解释

考虑选择 $i = 1$ 进行操作，操作后序列 $A=(2,1,1)$ 不是 good 的，因此该操作不可行。

再考虑选择 $i = 2$ 进行操作，操作后序列 $A=(1,1,2)$ 是 good 的，因此该操作可行。
可能得到的不同序列有 $A=(1,2,1)$ 和 $A=(1,1,2)$，因此答案是 $2$。

Translate by 宋怡芃