ストーリー

「ここでサヨナラしても, またどこかできっと会えるよね?」

問題文

$(N+1)$ 頂点からなる根付き木がある. $(N+1)$ 個の頂点は $0,1,2,\dots,N$ と番号付けられている. 根は頂点 $0$ であり, 頂点 $i~(1 \leq i \leq N)$ の親は頂点 $P_i~(0 \leq P_i \lt i)$ である.

チェリーちゃんは最初, 頂点 $0$ にいる.

チェリーちゃんは以下のルールに従って, 頂点の移動を何回か行う.

• チェリーちゃんがいる頂点が葉ではない場合: その頂点の子のいずれかに移動する. 移動先は $W_i$ に比例する確率で選ばれる.
  • 厳密には, その頂点の子が $u_1, u_2, \dots, u_l$ であるとき, $u_i$ が次の移動先として選ばれる確率は $\dfrac{W_{u_i}}{W_{u_1}+W_{u_2}+\dots+W_{u_l}}$ である.
  また, この場合における移動先の選択については各移動毎に独立であるとする.
• チェリーちゃんがいる頂点が葉である場合: 根 (頂点 $0$) に移動する.

このとき, 以下の $Q$ 個の質問 $q~(1 \leq q \leq Q)$ に答えよ.

• 質問 $q$ : チェリーちゃんが上記の移動を $K_q$ 回行った際, 頂点 $A_q$ が移動先として選ばれる回数の期待値を $E$ とする. このとき, $E \pmod{998244353}$ を求めよ.

注記

この問題の制約下においては, 各質問における $E$ に対して, $X \times E=Y$ となる $998244353$ の倍数ではない整数 $X$ と整数 $Y$ が存在する.

この $X,Y$ に対して, $X \times Z \equiv Y \pmod{998244353}$ となる $0$ 以上 $998244353$ 未満の整数 $Z$ が唯一存在するので, この $Z$ を用いて, $E \pmod{998244353}:=Z$ とする.

なお, $X \times E =Y$ となる $998244353$ の倍数ではない整数 $X$ と整数 $Y$ は数多に考えられるが, $Z$ は $X,Y$ の取り方によらず, $E$ にのみによって決まる.

制約

• $1 \leq N \leq 5000$.
• $0 \leq P_i \lt i \quad (0 \leq i \leq N)$.
• $1 \leq W_i \leq 10^5 \quad (0 \leq i \leq N)$.
• $1 \leq Q \leq 20$.
• $0 \leq A_q \leq N \quad (1 \leq q \leq Q)$.
• $0 \leq K_q \leq 10^9 \quad (1 \leq q \leq Q)$.
• 入力は全て整数である.

入力

$N$
$P_1$ $P_2$ $\dots$ $P_N$
$W_1$ $W_2$ $\dots$ $W_N$
$Q$
$A_1$ $K_1$
$A_2$ $K_2$
$\vdots$
$A_Q$ $K_Q$

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行目には, 質問 $q$ に対する解答を整数で $1$ 行に出力せよ.

最後に改行を忘れないこと.

サンプル

3
0 0 2
1 2 3
4
0 3
1 3
2 3
3 3

1
776412275
554580197
665496236

1
0
46
4
0 46
1 46
0 0
1 0

23
23
0
0

15
0 1 2 2 3 1 4 6 8 9 1 11 8 10 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
0 20150821
1 20160406
2 20160810
3 20161130
4 20170405
10 20170719
5 20171025
6 20180307
7 20180815
8 20190227
11 20200821
12 20201007
0 20201014
1 20201209
2 20210414
3 20211013
4 20220406
13 20220803
14 20221108
15 20221109

984593583
66562935
853150486
450394280
487556810
425770516
164383442
737722434
878250685
64190509
176934106
581447838
504103921
609099868
775475173
525420298
255941538
712197622
537846225
240794030