再次凑出 10

题目描述

我们有 $N$ 个骰子。 对于每个 $i = 1, 2, \ldots, N$,第 $i$ 个骰子掷出时,以等概率显示 $1$ 到 $A_i$ 之间的随机整数。

当 $N$ 个骰子同时掷出时,求满足以下条件的概率,对 $998244353$ 取模:

存在一种方式从这 $N$ 个骰子中选出若干个(可能全部),使得它们的点数之和为 $10$。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

样例

4
1 7 2 9

942786334

例如,如果第 1、2、3、4 个骰子分别显示 $1$、$3$、$2$、$7$,则这些结果满足条件。 事实上,如果选择第 2 个和第 4 个骰子,它们的点数之和为 $3+7=10$。 或者,如果选择第 1、3、4 个骰子,点数之和为 $1+2+7=10$。

另一方面,如果第 1、2、3、4 个骰子分别显示 $1$、$6$、$1$、$5$,则不存在选择其中若干个使点数之和为 $10$ 的方式,因此条件不被满足。

在该样例输入中,$N$ 个骰子的结果满足条件的概率为 $\dfrac{11}{18}$。 因此,输出这个值对 $998244353$ 取模的结果,即 $942786334$。

7
1 10 100 1000 10000 100000 1000000

996117877

数据范围

• $1 \le N \le 100$
• $1 \le A_i \le 10^6$
• 输入中的所有值均为整数。

提示

可以证明所求概率总是有理数。此外,该问题的约束保证了当所求概率表示为不可约分数 $\dfrac{y}{x}$ 时,$x$ 不被 $998244353$ 整除。

这里,存在唯一的整数 $z$ 使得 $xz \equiv y \pmod{998244353}$。输出这个 $z$。