Migrated from Lutece 2797 电子竞技大学

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

时间来到了2022年暑假，LPL 季后赛进入了白热化阶段。电子竞技大学的很多同学都喜欢看比赛，ljj 也是其中一个，他很喜欢在每天集训结束的晚上看比赛。

现在 ljj 把每只队伍的实力估算为 $x_{i}$。现在假定 LPL 采用循环赛制，每两个队伍之间都要进行一场比赛。假设参加某场比赛的两只队伍编号分别为 $i$ 和 $j$ ，那么 $i$ 战胜 $j$ 的概率是 $\frac{x_{i}}{x_{i}+x_{j}}$， $j$ 战胜 $i$ 的概率是 $\frac{x_{j}}{x_{i}+x_{j}}$。

当一个队伍可以直接或间接战胜其他所有队伍时，ljj 认为这个队伍具有出线实力。A 队能间接战胜 B 队，仅当存在一个队伍序列 $t_{1},t_{2},...,t_{m}$ ，满足 $t_{1}=A,t_{m}=B$ ，且 对于 $1\le i\le k$，$t_{i}$ 战胜了 $t_{i+1}$。类似于 "我单杀了石头人，石头人单杀faker，所以我也能单杀faker" 的逻辑。

现在 ljj 想知道，具有出线实力的队伍期望数量是多少？因为 ljj 还想看比赛，于是他把这个问题丢给了你。

Input

第一行读入一个整数 $n$，表示队伍数

第二行读入 $n$ 个整数，代表 ljj 对队伍实力的估算值

Output

输出一个整数表示具有出线实力的队伍的期望数量，请你输出这个值取模 998244353

tips：小数取模可以参考 oiwiki 或其他博客中关于逆元，费马小定理等数论算法的资料，注意 998244353 是一个质数，只需要学习模质数的逆元即可。

Samples

3
675969 948862 40692

15082370

2
1 2

1

5
1 2 8 11 14

462074775

Constraints

$2\le n\le 16, x_{i}\le 10^{6}$

Note

本题中使用复杂度更优的做法可以获得150%的分数，优秀的做法速度在500ms左右

Resources

2022 UESTC ICPC Training for Dynamic Programming