/ 
Time Limit: 7 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
1 から N までの番号のついた N 頂点からなる根付き木があります． 根は頂点 1 で，頂点 i (2 \leq i \leq N) の親は頂点 P_i (P_i<i) です．
また，1 以上 N 以下の整数からなる長さ M の整数列 A=(A_1,A_2,\cdots,A_M),B=(B_1,B_2,\cdots,B_M) があります．
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 である必要がある．
A に 0 回以上操作を行った結果としてあり得る数列の個数を 998244353 で割ったあまりを求めてください．
制約
- 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 の先祖であるかまたは 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 を選ぶことを考えます．操作後の A=(2,1,1) は good でないので，この操作は実行不可能です．
i=2 を選ぶことを考えます．操作後の A=(1,1,2) は good なので，この操作は実行可能です．
A に 0 回以上操作を行った結果としてあり得る数列は A=(1,2,1),(1,1,2) の 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
Score : 900 points
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.
Sample Input 1
3 3 1 2 1 2 1 1 2 3
Sample Output 1
2
Consider choosing i=1. The A=(2,1,1) after the operation is not good, so this operation is invalid.
Consider choosing i=2. The A=(1,1,2) after the operation is good, so this operation is valid.
There are two sequences that can result from performing zero or more operations on A: A=(1,2,1) and (1,1,2).
Sample Input 2
4 3 1 1 1 2 3 4 2 3 4
Sample Output 2
1
Sample Input 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
Sample Output 3
8
Sample Input 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
Sample Output 4
60