Problem Statement

There is a rooted tree with $N$ vertices numbered from $1$ to $N$. The root is vertex $1$, and the parent of vertex $i$ ($2 \leq i \leq N$) is vertex $P_i$ ($P_i<i$).

There are also integer sequences of length $M$: $A=(A_1,A_2,\cdots,A_M)$ and $B=(B_1,B_2,\cdots,B_M)$, consisting of integers between $1$ and $N$, inclusive.

$A$ is said to be good if and only if for each $i$, vertex $A_i$ is an ancestor of vertex $B_i$ or $A_i=B_i$. Initially, $A$ is good.

Consider the following operation on $A$.

• Choose an integer $i$ ($1 \leq i \leq M-1$) and swap the values of $A_i$ and $A_{i+1}$. Here, $A$ must remain good after the operation.

Find the number, modulo $998244353$, of sequences that can result from performing this operation on $A$ zero or more times.

Constraints

• $2 \leq N \leq 250000$
• $2 \leq M \leq 250000$
• $1 \leq P_i <i$
• $1 \leq A_i \leq B_i \leq N$
• Vertex $A_i$ is an ancestor of vertex $B_i$ or $A_i=B_i$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.