{"raw_statement":[{"iden":"problem statement","content":"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$).\nThere 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.\n$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.\nConsider the following operation on $A$.\n\n*   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.\n\nFind the number, modulo $998244353$, of sequences that can result from performing this operation on $A$ zero or more times."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 250000$\n*   $2 \\leq M \\leq 250000$\n*   $1 \\leq P_i <i$\n*   $1 \\leq A_i \\leq B_i \\leq N$\n*   Vertex $A_i$ is an ancestor of vertex $B_i$ or $A_i=B_i$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$P_2$ $P_3$ $\\cdots$ $P_N$\n$A_1$ $A_2$ $\\cdots$ $A_M$\n$B_1$ $B_2$ $\\cdots$ $B_M$"},{"iden":"sample input 1","content":"3 3\n1 2\n1 2 1\n1 2 3"},{"iden":"sample output 1","content":"2\n\nConsider choosing $i=1$. The $A=(2,1,1)$ after the operation is not good, so this operation is invalid.\nConsider choosing $i=2$. The $A=(1,1,2)$ after the operation is good, so this operation is valid.\nThere are two sequences that can result from performing zero or more operations on $A$: $A=(1,2,1)$ and $(1,1,2)$."},{"iden":"sample input 2","content":"4 3\n1 1 1\n2 3 4\n2 3 4"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"8 13\n1 2 2 3 4 4 3\n5 3 2 5 4 6 2 8 2 6 7 4 7\n5 5 8 5 6 6 5 8 3 6 7 4 7"},{"iden":"sample output 3","content":"8"},{"iden":"sample input 4","content":"30 27\n1 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\n1 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\n14 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"},{"iden":"sample output 4","content":"60"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}