Problem Description

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 $).

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

A sequence $ A $ is good 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} $. However, the resulting $ A $ must also be good.

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

Input Format

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 Format

Output the answer.

Sample Input and Output

Sample Input #1

3 3
1 2
1 2 1
1 2 3

Sample Output #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

Notes/Hints

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 values given in the input are integers

Sample Explanation 1

Consider choosing $ i = 1 $. After the operation, $ A = (2, 1, 1) $ is not good, so this operation is not feasible. Consider choosing $ i = 2 $. After the operation, $ A = (1, 1, 2) $ is good, so this operation is feasible. The possible sequences that can result from zero or more operations on $ A $ are $ A = (1, 2, 1), (1, 1, 2) $, which are two in total.

见题面 Input 部分

见题面 Output 部分