← 返回题目列表

AtCoder · abc310_f

I. 再次制作 10

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有 N 骰子。 对于每个 i = 1, 2, \ldots, N,当 i-第一个骰子被抛出,它显示了一个介于 1 和 A_i,包含在内,概率相等。

求概率,模 998244353,当满足以下条件时 N 骰子同时投掷。

有一种方法可以选择一些(可能是全部) N 骰子,其结果之和为 10.

如何求概率模 998244353

可以证明,求的概率总是有理数。此外,该问题的约束保证如果所寻求的概率表示为不可约分数 \frac{y}{x},那么 x 不能被整除 998244353.

这里有一个唯一的整数 z 这样 xz \equiv y \pmod{998244353}。报告此事 z.

约束

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 10^6
  • 所有输入值均为整数。

输入

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

N
A_1 A_2 \ldots A_N

输出

打印答案。


样本输入 1

4
1 7 2 9

示例输出 1

942786334

例如,如果第一个、第二个、第三个和第四个骰子显示 1, 3, 2,和 7,这些结果分别满足条件。 事实上,如果选择第二个和第四个骰子,它们的结果之和就是 3 + 7 = 10。 或者,如果选择了第一个、第三个和第四个骰子,则它们的结果之和为 1 + 2 + 7 = 10.

另一方面,如果第一个、第二个、第三个和第四个骰子显示 1, 6, 1,和 5分别,没有办法选择其中的一些,使得它们的结果之和为 10,因此条件不满足。

在此示例输入中,结果的概率 N 满足条件的骰子是 \frac{11}{18}。 因此,打印这个值模 998244353,即 942786334.


示例输入 2

7
1 10 100 1000 10000 100000 1000000

示例输出 2

996117877