← 返回题目列表

Codeforces · 913/H

H. 不要超过

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

生成实数 s1, s2, ..., sn,如下所示:

- s0 = 0;
- si = si - 1 + ti,其中ti是在0和1(含)之间随机独立均匀选择的实数。

给定实数 x1, x2, ..., xn。您感兴趣的是 si ≤ xi 对于所有 i 同时成立的概率。

可以证明,这可以表示为 $$\frac{p}{q}$$,其中 P 和 Q 是互质整数,$$Q \not\equiv 0 \pmod{998244353}$$。打印 P·Q - 1 模 998244353 的值。

输入

第一行包含整数 n (1 ≤ n ≤ 30)。

接下来的 n 行包含实数 x1, x2, ..., xn,小数点后最多有六位数字 (0 < xi ≤ n)。

输出

打印一个整数,即问题的答案。

示例

输入 #1

4
1.00
2
3.000000
4.0

输出 #1

1

输入 #2

1
0.50216

输出 #2

342677322

输入 #3

2
0.5
1.0

输出 #3

623902721

输入#4

6
0.77
1.234567
2.1
1.890
2.9999
3.77

输出#4

859831967

注意

在第一个示例中,所寻求的概率为 1,因为 i 个不超过 1 的实数之和不超过 i。

在第二个示例中,概率本身就是 x1。

在第三个示例中,寻求的概率是 3 / 8。