Good Contest
Contest: Educational Codeforces Round 81 (Rated for Div. 2)
Difficulty rating: 2700
Tags: combinatorics, dp, probabilities

An online contest will soon be held on ForceCoders, a large competitive programming platform. The authors have prepared $$$n$$$ problems; and since the platform is very popular, $$$998244351$$$ coder from all over the world is going to solve them.

For each problem, the authors estimated the number of people who would solve it: for the $$$i$$$-th problem, the number of accepted solutions will be between $$$l_i$$$ and $$$r_i$$$, inclusive.

The creator of ForceCoders uses different criteria to determine if the contest is good or bad. One of these criteria is the number of inversions in the problem order. An inversion is a pair of problems $$$(x, y)$$$ such that $$$x$$$ is located earlier in the contest ($$$x < y$$$), but the number of accepted solutions for $$$y$$$ is strictly greater.

Obviously, both the creator of ForceCoders and the authors of the contest want the contest to be good. Now they want to calculate the probability that there will be no inversions in the problem order, assuming that for each problem $$$i$$$, any integral number of accepted solutions for it (between $$$l_i$$$ and $$$r_i$$$) is equally probable, and all these numbers are independent.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of problems in the contest.

Then $$$n$$$ lines follow, the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 998244351$$$) — the minimum and maximum number of accepted solutions for the $$$i$$$-th problem, respectively.

Output format:
The probability that there will be no inversions in the contest can be expressed as an irreducible fraction $$$\frac{x}{y}$$$, where $$$y$$$ is coprime with $$$998244353$$$. Print one integer — the value of $$$xy^{-1}$$$, taken modulo $$$998244353$$$, where $$$y^{-1}$$$ is an integer such that $$$yy^{-1} \equiv 1$$$ $$$(mod$$$ $$$998244353)$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The real answer in the first test is $$$\frac{1}{2}$$$.

Example input:
3
1 2
1 2
1 2

Example output:
499122177

Example input:
2
42 1337
13 420

Example output:
578894053

Editorial:
Model solution (slow, complicated and not cool):
The naive solution is dynamic programming: let $$$dp_{i, x}$$$ be the probability that the first $$$i$$$ problems don't have any inversions, and the $$$i$$$-th one got $$$x$$$ accepted solutions. Let's somehow speed it up. For convenience, I will modify the variable denoting the maximum number of accepted solutions for each problem: $$$L_i = l_i$$$, $$$R_i = r_i + 1$$$; and I will also reverse the problem order, so that we don't want the number of solutions to decrease from problem to problem.
We know that $$$dp_{i, x} = \frac{1}{R_i - L_i} \sum\limits_{j = 0}^{x} dp_{i - 1, j}$$$, if $$$x \in [L_i, R_i)$$$, and $$$dp_{i, x} = 0$$$ otherwise. Let's divide the whole segment between $$$0$$$ and $$$998244351$$$ into $$$O(n)$$$ segments with the values of $$$L_i$$$ and $$$R_i$$$ and analyse the behavior of $$$dp$$$ values on each such segment.
Let $$$f_i(x) = dp_{i, x}$$$. If we consider the behavior of $$$f_i(x)$$$ on some segment we got, we can prove by induction that it is a polynomial of degree not exceeding $$$i$$$.
All that is left is to carefully calculate and maintain these polynomials on segments. The main thing we will use to calculate the polynomials is interpolation. To transition from $$$f_i$$$ to $$$f_{i + 1}$$$, we will consider each segment separately, calculate the first several values of $$$f_{i + 1}$$$ on each segment (we need to calculate the sum $$$\sum\limits_{x = L}^{R} P(x)$$$ fast, if $$$P(x)$$$ is a polynomial, this can also be done with interpolation), and then interpolate it on the whole segment.
This is actually slow (we have to interpolate at least $$$O(n^2)$$$ polynomials) and not easy to write. Let's consider a better solution.
Participants' solution (much faster and easier to code):
We will use combinatoric approach: instead of calculating probabilities, we will count all the non-descending sequences $$$(a_1, a_2, \dots, a_n)$$$ such that $$$i \in [L_i, R_i)$$$, and divide it by the number of all sequences without the non-descending condition (that is just $$$\prod_{i=1}^{n} R_i - L_i$$$).
Let's again divide $$$[0, 998244353]$$$ into $$$O(n)$$$ segments using the points $$$L_i$$$, $$$R_i$$$, and enumerate these segments from left to right. If there are two neighboring values $$$a_i$$$ and $$$a_{i + 1}$$$, they either belong to the same segment, or the segment $$$a_{i + 1}$$$ belongs to is to the right of the segment $$$a_i$$$ belongs to.
We could try to write the following dynamic programming solution: $$$cnt_{i, j}$$$ is the number of non-descending prefixes of the sequence such that there are $$$i$$$ elements in the prefix, and the last one belongs to segment $$$j$$$. It's easy to model transitions from $$$cnt_{i, j}$$$ to $$$cnt_{i + 1, k}$$$ where $$$k > j$$$, but we don't know how to model the transition to $$$cnt_{i + 1, j}$$$.
Let's get rid of them altogether! We will introduce an additional constraint in our dynamic programming: $$$cnt_{i, j}$$$ is the number of prefixes of the sequence of length $$$i$$$ such that all elements on prefix belong to one of the first $$$j$$$ segments, but next element should not belong to it. The transitions in this dynamic programming are different: we iterate on the number of elements $$$k$$$ belonging to the next segment and transition into $$$cnt_{i + k, j + 1}$$$ (if possible). Calculating the number of ways to take $$$k$$$ elements from an interval $$$[L, R)$$$ in sorted order can be reduced to calculating the number of ways to compose $$$k$$$ as the sum of $$$R - L$$$ non-negative summands (order matters). We should be able to calculate binomial coefficients with fairly large $$$n$$$ and not so large $$$k$$$, but that's not really hard if we use the formula $$$\binom{n}{k} = \binom{n}{k - 1} \cdot \frac{n - k + 1}{k}$$$.