{"problem":{"name":"Sum of Hash of Lexmin","description":{"content":"There is a rooted tree $T$ with $N$ vertices numbered from $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ ($2 \\leq i \\leq N$) is $P_i$ ($P_i < i$). A permutation $x = (x_1, x_2, \\cdo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc068_d"},"statements":[{"statement_type":"Markdown","content":"There is a rooted tree $T$ with $N$ vertices numbered from $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ ($2 \\leq i \\leq N$) is $P_i$ ($P_i < i$).\nA permutation $x = (x_1, x_2, \\cdots, x_N)$ of $(1, 2, \\cdots, N)$ is judged to be a **good** permutation or not by the following criteria.\n\n*   Consider the following operation on $x$.\n    *   Choose two adjacent elements $u$ and $v$ in $x$ such that $u$ and $v$ are in an ancestor-descendant relationship in $T$. It does not matter which is the ancestor and which is the descendant. Then, swap $u$ and $v$.\n*   If it is possible to obtain a permutation that is lexicographically strictly smaller than the initial state by performing the above operation zero or more times, $x$ is **not** a good permutation. If it is impossible to obtain a permutation lexicographically smaller than the initial state by any such operations, $x$ is a good permutation.\n\nYou are given a positive integer $B$. For a permutation $x$, define $\\operatorname{hash}(x) = \\sum_{1 \\leq i \\leq N} B^{i-1} \\times x_i$.\nFind the sum of $\\operatorname{hash}(x)$ over all good permutations $x$, modulo $998244353$.\nWhat is lexicographical order on sequences?A sequence $S = (S_1, S_2, \\ldots, S_{|S|})$ is said to be **lexicographically smaller** than a sequence $T = (T_1, T_2, \\ldots, T_{|T|})$ if and only if 1. or 2. below holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $(S_1, S_2, \\ldots, S_{|S|}) = (T_1, T_2, \\ldots, T_{|S|})$.\n2.  There exists an integer $1 \\leq i \\leq \\min{ |S|, |T| }$ such that the following two statements hold.\n    *   $(S_1, S_2, \\ldots, S_{i-1}) = (T_1, T_2, \\ldots, T_{i-1})$.\n    *   $S_i$ is smaller than $T_i$ (as a number).\n\n## Constraints\n\n*   $2 \\leq N \\leq 100$\n*   $1 \\leq B < 998244353$\n*   $1 \\leq P_i < i$ ($2 \\leq i \\leq N$)\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $B$\n$P_2$ $P_3$ $\\cdots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc068_d","tags":[],"sample_group":[["3 100\n1 1","50502\n\nFor example, $x = (3, 1, 2)$ is not a good permutation, because by swapping $3$ and $1$, which are in an ancestor-descendant relationship, we can obtain $(1, 3, 2)$, a lexicographically smaller permutation.\nIn this sample, the good permutations are $x = (1, 2, 3)$ and $x = (1, 3, 2)$. Thus, the answer is $\\operatorname{hash}((1,2,3)) + \\operatorname{hash}((1,3,2)) = 30201 + 20301 = 50502$."],["5 100\n1 2 3 4","504030201\n\nIn this sample, any two vertices are in an ancestor-descendant relationship. Therefore, the only good permutation is $x = (1, 2, 3, 4, 5)$."],["10 248730679\n1 2 1 2 5 6 1 8 1","856673861"],["20 480124393\n1 2 3 2 3 4 3 8 3 4 11 10 4 14 15 12 17 18 19","488941820"]],"created_at":"2026-03-03 11:01:14"}}