2.1 题目描述

众所周知，$\texttt{w}{\color{red}\texttt{asa855}}$ 是个人赢，有 $249999!$ 个妹子，但作为一个超强的 OIer，他怎可能只有妹子呢？他不仅有很多毒瘤的构造题，还有很多树。现在 $\texttt{w}{\color{red}\texttt{asa855}}$ 想给每个妹子整一棵树，点 $i$ 有权值 $a_i$，一个妹子认为她在 $\texttt{w}{\color{red}\texttt{asa855}}$ 心里的重要程度为 $\displaystyle \prod_{v\in \operatorname{subtree(lca}(n-1,n))}a_v$，现在 $\texttt{w}{\color{red}\texttt{asa855}}$ 想知道他妹子的重要程度之和，以便计算还能找多少个妹子，忙着出毒瘤构造题的 $\texttt{w}{\color{red}\texttt{asa855}}$ 决定找你帮忙。

树的生成方式为： $i$ 的父节点 $p_i$ 是 $[1,i)$ 中一个整数。 求 $(n-1)!$ 种可能的树的权值和 $\bmod998244353$。

2.2 输入格式

第一行一个数 $n$ 第二行 $n$ 个数，$a_1,a_2,...,a_n$

2.3 输出格式

一行一个非负整数，表示答案。

2.4 样例 1 输入

3
1 1 1

2.5 样例 1 输出

2

2.6 样例 2 输入

12
1 1 4 5 1 4 1 9 1 9 8 1

2.7 样例 2 输出

565299753

2.8 限制与约定

$\text{subtask1(10 pts):}\ n\le 10$

$\text{subtask2(20 pts):}\ n\le 500$

$\text{subtask3(20 pts):}\ n\le 5000$

$\text{subtask4(10 pts):}$ $a_i$ 全部相等

$\text{subtask5(40 pts):}$ 无特殊限制

对于 $100\%$ 的数据 $3\le n \le 250000,1 \le a_i < 998244353$