AT_abc459_e [ABC459E] Select from Subtrees

$ N $ 頂点の根付き木 $ T $ があり、各頂点は頂点 $ 1 $ , 頂点 $ 2 $ , $ \ldots $ , 頂点 $ N $ と番号づけられています。 頂点 $ 1 $ は $ T $ の根であり、頂点 $ i $ $ (2\leq i\leq N) $ の（直接の）親は $ P_i $ です。 また、頂点 $ i $ $ (1\leq i\leq N) $ には $ C_i $ 個のアメがあります。 ここで、 $ (C_1+C_2+\cdots+C_N) $ 個のアメはすべて区別されます。 高橋君は $ N $ 匹のリスに命令を出しました。 具体的には、 $ i $ 匹目 $ (1\leq i\leq N) $ のリスに次の命令を出しました。 - 頂点 $ i $ を根とした部分木から $ D_i $ 個のアメを選んで取ってくる。 異なるリスが同じアメを取ることはできません。 アメの選ばれ方としてあり得るものの個数を $ 998244353 $ で割った余りを出力してください。 ここで、最終的に選ばれたアメの集合が同じであっても、選んだリスが異なっていれば、異なる選ばれ方として数えるものとします。 また、すべてのリスが命令通りにアメを持ってくることが不可能な場合は $ 0 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_2 $ $ P_3 $ $ \ldots $ $ P_N $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_N $ $ D_1 $ $ D_2 $ $ \ldots $ $ D_N $

アメの選ばれ方としてあり得るものの個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 頂点 $ 1,2,3,4,5 $ にあるアメをそれぞれアメ $ 1 $ , アメ $ 2\cdot 3 $ , アメ $ 4 $ , アメ $ 5\cdot 6 $ , アメ $ 7\cdot 8\cdot 9 $ とします。 アメの選ばれ方としては例えば次のようなものが考えられます。 - リス $ 1 $ が頂点 $ 1 $ を根とした（頂点 $ 1,2,3,4,5 $ からなる）木からアメ $ 3 $ を持ってくる。 - リス $ 2 $ が頂点 $ 2 $ を根とした（頂点 $ 2 $ からなる）木からアメ $ 2 $ を持ってくる。 - リス $ 3 $ が頂点 $ 3 $ を根とした（頂点 $ 3,4,5 $ からなる）木からアメ $ 4,7,9 $ を持ってくる。 - リス $ 4 $ が頂点 $ 4 $ を根とした（頂点 $ 4 $ のみからなる）木からアメ $ 6 $ を持ってくる。 - リス $ 5 $ が頂点 $ 5 $ を根とした（頂点 $ 5 $ のみからなる）木からアメ $ 8 $ を持ってくる。 なお、これは以下のような選ばれ方とは区別されます。 - リス $ 1 $ が頂点 $ 1 $ を根とした（頂点 $ 1,2,3,4,5 $ からなる）木からアメ $ \mathbf{2} $ を持ってくる。 - リス $ 2 $ が頂点 $ 2 $ を根とした（頂点 $ 2 $ からなる）木からアメ $ \mathbf{3} $ を持ってくる。 - リス $ 3 $ が頂点 $ 3 $ を根とした（頂点 $ 3,4,5 $ からなる）木からアメ $ 4,7,9 $ を持ってくる。 - リス $ 4 $ が頂点 $ 4 $ を根とした（頂点 $ 4 $ のみからなる）木からアメ $ 6 $ を持ってくる。 - リス $ 5 $ が頂点 $ 5 $ を根とした（頂点 $ 5 $ のみからなる）木からアメ $ 8 $ を持ってくる。 条件をみたす選び方は全部で $ 144 $ 通りあるため、 $ 144 $ を $ 998244353 $ で割った余りである $ 144 $ を出力します。 ### Sample Explanation 2 木には頂点 $ 1 $ と頂点 $ 2 $ あわせて $ 2 $ 個しかアメがないため、両方のリスが命令通りにアメを選ぶことはできません。 よって、 $ 0 $ を出力します。 ### Sample Explanation 3 $ 998244353 $ で割った余りを出力することに注意してください。 ### Constraints - $ 2\leq N\leq 2\times 10^5 $ - $ 1\leq P_i\leq N $ - $ 1\leq C_i\leq 10^9 $ - $ 1\leq D_i $ - $ D_1+D_2+\cdots+D_N\leq 10^6 $ - 入力はすべて整数 - $ T $ は頂点 $ 1 $ を根とした根付き木