← 返回题目列表

Codeforces · 1295/F

F. 好比赛

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

一场在线竞赛即将在大型编程竞赛平台 ForceCoders 上举行。作者准备了$$$n$$$问题;由于该平台非常受欢迎,来自世界各地的 $$$998244351$$$ 编码员将解决这些问题。

对于每个问题,作者估计了能够解决该问题的人数:对于第 $$$i$$$ 问题,接受的解决方案数量将在 $$$l_i$$$ 和 $$$r_i$$$(含)之间。

ForceCoders 的创建者使用不同的标准来确定比赛的好坏。这些标准之一是问题顺序中的倒置次数。反演是一对问题 $$$(x, y)$$$,使得 $$$x$$$ 位于竞赛的较早位置 ($$$x < y$$$),但 $$$y$$$ 接受的解决方案数量严格更多。

显然,ForceCoders 的创建者和竞赛的作者都希望竞赛办得好。现在,他们想要计算问题顺序中不存在反转的概率,假设对于每个问题 $$$i$$$,任何整数个可接受的解决方案(在 $$$l_i$$$ 和 $$$r_i$$$ 之间)都是同等概率的,并且所有这些数字都是独立的。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 竞赛中的问题数。

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 998244351$$$) — 分别是第 $$$i$$$ 问题的可接受解的最小和最大数量。

输出

比赛中不存在反转的概率可以表示为不可约分数 $$$\frac{x}{y}$$$,其中 $$$y$$$ 与 $$$998244353$$$ 互质。打印一个整数 — $$$xy^{-1}$$$ 的值,以 $$$998244353$$$ 为模,其中 $$$y^{-1}$$$ 是一个整数,使得 $$$yy^{-1} \equiv 1$$$ $$$(mod$$$ $$$998244353)$$$。

示例

输入 #1

3
1 2
1 2
1 2

输出 #1

499122177

输入 #2

2
42 1337
13 420

输出 #2

578894053

输入 #3

2
1 1
0 0

输出 #3

1

输入#4

2
1 1
1 1

输出#4

1

注意

第一个测试中的真实答案是 $$$\frac{1}{2}$$$。