一场在线竞赛即将在大型编程竞赛平台 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}$$$。