[PKUWC2018] 猎人杀

题目描述

猎人杀是一款风靡一时的游戏“狼人杀”的民间版本,他的规则是这样的: 一开始有 $n$ 个猎人,第 $i$ 个猎人有仇恨度 $w_i$ ,每个猎人只有一个固定的技能:死亡后必须开一枪,且被射中的人也会死亡。 然而向谁开枪也是有讲究的,假设当前还活着的猎人有 $[i_1\ldots i_m]$,那么有 $\frac{w_{i_k}}{\sum_{j = 1}^{m} w_{i_j}}$ 的概率是向猎人 $i_k$ 开枪。 一开始第一枪由你打响,目标的选择方法和猎人一样(即有 $\frac{w_i}{\sum_{j=1}^{n}w_j}$ 的概率射中第 $i$ 个猎人)。由于开枪导致的连锁反应,所有猎人最终都会死亡,现在 $1$ 号猎人想知道它是最后一个死的的概率。 答案对 $998244353$ 取模。

输入输出格式

输入格式


第一行一个正整数 $n$; 第二行 $n$ 个正整数,第 $i$ 个正整数表示 $w_i$。

输出格式


输出答案。

输入输出样例

输入样例 #1

3
1 1 2

输出样例 #1

915057324

说明

#### 样例解释 答案是 $\frac{2}{4}\times \frac{1}{2}+\frac{1}{4}\times \frac{2}{3}=\frac{10}{24}$。 对于 $10\%$ 的数据,有 $1\leq n\leq 10$ 对于 $30\%$ 的数据,有 $1\leq n\leq 20$ 对于 $50\%$ 的数据,有 $1\leq \sum\limits_{i=1}^{n}w_i\leq 5000$ 另有 $10\%$ 的数据,满足 $1\leq w_i\leq 2$,且 $w_1=1$ 另有 $10\%$ 的数据,满足 $1\leq w_i\leq 2$,且 $w_1=2$ 对于 $100\%$ 的数据,有 $w_i>0$,且 $1\leq \sum\limits_{i=1}^{n}w_i \leq 100000$