P17786 小糸侑不是罪过

『对不起。』

定义一个由编号为 $1\sim n$ 的点构成的有根树是合法的，当且仅当满足以下条件： - 编号为 $1$ 的点是根。 - 记 $f_x$ 为编号为 $x$ 的点其父亲的编号。则对于 $x\in [2,n]$，均有 $f_x < x$。 对一棵合法的有根树 $T$： - 定义点 $i$ 的重儿子 $h_i$ 为： $i$ 所有儿子中编号的最大值。 - 定义树 $T$ 的重链剖分为：对每个非叶子节点（根节点不算叶子节点）仅保留其与其重儿子之间的连边时，得到的子图 $G$。显然，$G$ 中每个连通块都是 $T$ 中一条自上而下的链。 - 定义树 $T$ 的剖分价值为：记其重链剖分后得到的子图 $G$ 包含的连通块为 $s_1,s_2,\dots, s_k$，其中 $s_i$ 为第 $i$ 个连通块内点编号构成的集合。则 $T$ 的剖分价值等于 $\prod\limits_{i=1}^{k}(|s_i|+\sum\limits_{x\in s_i}^{}val_x)$。其中 $val$ 为一个长度为 $n$ 的序列。 现给定 $n$ 和序列 $val_{1\sim n}$。求所有合法的树 $T$ 的剖分价值之和对 $998244353$ 取模的结果。

第一行一个整数 $n$。 第二行 $n$ 个整数 $val_{1\sim n}$。

一行一个整数表示答案。

保证 $2 \le n \le 500,0\le val_i \le 10^8$。