AT_arc195_e [ARC195E] Random Tree Distance

整数列 $ A = (A_2,A_3,\ldots,A_N) $ があります。また、各 $ i $ $ (2 \leq i \leq N) $ について $ 1 \leq P_i \leq i-1 $ を満たす整数列 $ P=(P_2, P_3, \ldots ,P_N) $ に対して、頂点 $ 1 $ を根とする $ N $ 頂点の重み付き木 $ T(P) $ を以下のように定義します。 - 各 $ i $ $ (2 \leq i \leq N) $ について、 $ i $ の親が $ P_i $ であり、 $ i $ と $ P_i $ を結ぶ辺の重みが $ A_i $ であるような根付き木 $ Q $ 個のクエリが与えられるので、順に処理してください。 $ i $ 番目のクエリは以下の通りです。 - $ 1 $ 以上 $ N $ 以下の整数 $ u_i,v_i $ が与えられる。 $ P $ としてあり得る $ (N-1)! $ 通りの数列全てについての木 $ T(P) $ での頂点 $ u_i $ と頂点 $ v_i $ の距離の総和を $ 998244353 $ で割った余りを出力する。ただし、頂点 $ u_i $ と頂点 $ v_i $ の距離とは、この $ 2 $ 頂点を結ぶ唯一の（同じ頂点を $ 2 $ 回以上通らない）パスに含まれる辺の重みの総和である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_2 $ $ A_3 $ $ \ldots $ $ A_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_Q $ $ v_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 - $ P = (1,1) $ の場合、木 $ T(P) $ での頂点 $ 1 $ と頂点 $ 2 $ の距離は $ 1 $ 、頂点 $ 1 $ と頂点 $ 3 $ の距離は $ 1 $ です。 - $ P = (1,2) $ の場合、木 $ T(P) $ での頂点 $ 1 $ と頂点 $ 2 $ の距離は $ 1 $ 、頂点 $ 1 $ と頂点 $ 3 $ の距離は $ 2 $ です。 以上より、全ての $ P $ に対する木 $ T(P) $ での頂点 $ 1 $ と頂点 $ 2 $ の距離の総和は $ 2 $ 、頂点 $ 1 $ と頂点 $ 3 $ の距離の総和は $ 3 $ です。 ### Sample Explanation 3 総和を $ 998244353 $ で割った余りを求めることに注意してください。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - $ 1 \leq u_i \lt v_i \leq N $ - 入力される値は全て整数