{"raw_statement":[{"iden":"problem statement","content":"There is an integer sequence $A = (A_2,A_3,\\ldots,A_N)$. Also, for an integer sequence $P=(P_2, P_3, \\ldots ,P_N)$ where $1 \\leq P_i \\leq i-1$ for each $i$ $(2 \\leq i \\leq N)$, define the weighted tree $T(P)$ with $N$ vertices, rooted at vertex $1$, as follows:\n\n*   A rooted tree where, for each $i$ $(2 \\leq i \\leq N)$, the parent of $i$ is $P_i$, and the weight of the edge between $i$ and $P_i$ is $A_i$.\n\nYou are given $Q$ queries. Process them in order. The $i$\\-th query is as follows:\n\n*   You are given integers $u_i$ and $v_i$, each between $1$ and $N$. For each of the possible $(N-1)!$ sequences $P$, take the tree $T(P)$ and consider the distance between vertices $u_i$ and $v_i$ in this tree. Output the sum, modulo $998244353$, of these distances over all $T(P)$. Here, the distance between two vertices $u_i$ and $v_i$ is the sum of the weights of the edges on the unique path (not visiting the same vertex more than once) that connects them."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   $1 \\leq u_i < v_i \\leq N$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_2$ $A_3$ $\\ldots$ $A_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_Q$ $v_Q$"},{"iden":"sample input 1","content":"3 2\n1 1\n1 2\n1 3"},{"iden":"sample output 1","content":"2\n3\n\n*   If $P = (1,1)$, then in the tree $T(P)$, the distance between vertices $1$ and $2$ is $1$, and the distance between vertices $1$ and $3$ is $1$.\n*   If $P = (1,2)$, then in the tree $T(P)$, the distance between vertices $1$ and $2$ is $1$, and the distance between vertices $1$ and $3$ is $2$.\n\nTherefore, the total distance between vertices $1$ and $2$ over all $T(P)$ is $2$, and the total distance between vertices $1$ and $3$ over all $T(P)$ is $3$."},{"iden":"sample input 2","content":"2 1\n100\n1 2"},{"iden":"sample output 2","content":"100"},{"iden":"sample input 3","content":"9 6\n765689282 93267307 563699854 951829154 801512848 389123318 924504746 596035433\n3 8\n2 5\n5 8\n2 9\n8 9\n5 7"},{"iden":"sample output 3","content":"55973424\n496202632\n903509579\n343265517\n550981449\n68482696\n\nRemember to take the sum modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}