题目描述

有一棵以 $1$ 为根、包含 $N$ 个顶点的有根树 $T$，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根，对于每个 $2 \leq i \leq N$，顶点 $i$ 的父节点为 $P_i$（$P_i < i$）。

对于 $1$ 到 $N$ 的一个排列 $x=(x_1,x_2,\cdots,x_N)$，判断它是否为良好排列的方法如下：

• 对于排列 $x$，可以进行如下操作：
  • 选择排列中相邻的两个元素 $u,v$，如果 $u,v$ 在树 $T$ 上存在祖先-子孙关系（无论谁是祖先谁是子孙均可），则可以交换 $u,v$ 的位置。
• 如果经过若干次（可以为 $0$ 次）上述操作，能够得到一个字典序严格小于初始排列的排列，则 $x$ 不是良好排列。否则，$x$ 是良好排列。

给定正整数 $B$。对于排列 $x$，定义 $\operatorname{hash}(x)=\sum\_{1 \leq i \leq N} B^{i-1} \times x\_i$。

请计算所有良好排列 $x$ 的 $\operatorname{hash}(x)$ 之和，并对 $998244353$ 取模后输出。

数列的字典序定义如下：设 $S=(S_1,S_2,\ldots,S_{|S|})$，$T=(T_1,T_2,\ldots,T_{|T|})$，则 $S$ 的字典序小于 $T$ 当且仅当满足以下两条之一：

1. $|S| < |T|$ 且 $(S\_1,S\_2,\ldots,S\_{|S|}) = (T\_1,T\_2,\ldots,T\_{|S|})$。
2. 存在整数 $1 \leq i \leq \min\lbrace |S|,|T| \rbrace$，使得
   • $(S\_1,S\_2,\ldots,S\_{i-1}) = (T\_1,T\_2,\ldots,T\_{i-1})$，
   • $S_i < T_i$。

输入格式

输入为一行，格式如下：

$N$ $B$ $P_2$ $P_3$ $\cdots$ $P_N$

输出格式

输出答案。

样例 1

输入

3 100
1 1

输出

50502

样例 2

输入

5 100
1 2 3 4

输出

504030201

样例 3

输入

10 248730679
1 2 1 2 5 6 1 8 1

输出

856673861

样例 4

输入

20 480124393
1 2 3 2 3 4 3 8 3 4 11 10 4 14 15 12 17 18 19

输出

488941820

说明/提示

数据范围

• $2 \leq N \leq 100$
• $1 \leq B < 998244353$
• $1 \leq P_i < i$（$2 \leq i \leq N$）
• 输入的所有值均为整数

样例解释 1

例如，$x=(3,1,2)$ 不是良好排列。因为可以交换 $3,1$（它们在树上有祖先-子孙关系），得到 $x=(1,3,2)$，其字典序更小。在本样例中，良好排列为 $x=(1,2,3)$ 和 $x=(1,3,2)$ 共 $2$ 个。因此，$\operatorname{hash}((1,2,3))+\operatorname{hash}((1,3,2))=30201+20301=50502$，输出 $50502$。

样例解释 2

在本样例中，任意两个顶点都存在祖先-子孙关系。因此，唯一的良好排列为 $x=(1,2,3,4,5)$。

由 ChatGPT 4.1 翻译