Contest Duration: - (local time) (180 minutes) Back to Home
E - Child to Parent /

Time Limit: 4 sec / Memory Limit: 1024 MB

### 問題文

• i\geq 2 かつ A_i \geq 1 となる i をひとつ選ぶ．A_iA_i - 1 に，A_{P_i}A_{P_i}+r に置き換える．

### 制約

• 2\leq N\leq 300
• 1\leq P_i \leq i - 1 (2\leq i\leq N)
• 0\leq r \leq 10^9
• 0\leq A_i \leq 10^9

### 入力

N
P_2 \ldots P_N
r
A_1 \ldots A_N


### 入力例 1

3
1 1
2
1 1 1


### 出力例 1

4


### 入力例 2

3
1 2
1
1 1 1


### 出力例 2

5


### 入力例 3

3
1 2
2
1 1 1


### 出力例 3

6


### 入力例 4

5
1 1 3 3
2
0 1 0 1 2


### 出力例 4

48


### 入力例 5

5
1 1 3 3
123456789
1 2 3 4 5


### 出力例 5

87782255


Score : 1400 points

### Problem Statement

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

You are given a non-negative integer r and a sequence of non-negative integers A = (A_1, \ldots, A_N). You can perform the following operation on the sequence any number of times, possibly zero.

• Choose an i such that i\geq 2 and A_i \geq 1. Replace A_i with A_i - 1 and A_{P_i} with A_{P_i}+r.

Find the number, modulo 998244353, of possible final states of the sequence A.

### Constraints

• 2\leq N\leq 300
• 1\leq P_i \leq i - 1 (2\leq i\leq N)
• 0\leq r \leq 10^9
• 0\leq A_i \leq 10^9

### Input

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

N
P_2 \ldots P_N
r
A_1 \ldots A_N


### Output

Print the number, modulo 998244353, of possible final states of the sequence A.

### Sample Input 1

3
1 1
2
1 1 1


### Sample Output 1

4


The four possible final states of A are (1,1,1), (3,0,1), (3,1,0), and (5,0,0).

### Sample Input 2

3
1 2
1
1 1 1


### Sample Output 2

5


The five possible final states of A are (1,1,1), (1,2,0), (2,0,1), (2,1,0), and (3,0,0).

### Sample Input 3

3
1 2
2
1 1 1


### Sample Output 3

6


The six possible final states of A are (1,1,1), (1,3,0), (3,0,1), (3,2,0), (5,1,0), and (7,0,0).

### Sample Input 4

5
1 1 3 3
2
0 1 0 1 2


### Sample Output 4

48


### Sample Input 5

5
1 1 3 3
123456789
1 2 3 4 5


### Sample Output 5

87782255