Sum of Maximums Over Intervals

You are given n intervals \([p_i, q_i]\) for \(i=1,2,\ldots,n\). Consider all \(n\)-tuples \((s_1,s_2,\dots,s_n)\) where each \(s_i\) is an integer satisfying \(p_i \le s_i \le q_i\). Your task is to compute

\(\sum_{s_1=p_1}^{q_1} \sum_{s_2=p_2}^{q_2}\cdots\sum_{s_n=p_n}^{q_n}\max_{1 \le i \le n}\; s_i \pmod {998244353}\)

More formally, if we define a function \[ F(m)=\prod_{i=1}^n f_i(m)\quad\text{with}\quad f_i(m)=\begin{cases}0,& mq_i,\end{cases} \] then the answer is given by \[ \sum_{m=\min_i p_i}^{\max_i q_i} m\Bigl( F(m)-F(m-1)\Bigr) \pmod{998244353}. \]

inputFormat

The first line contains an integer \(n\) representing the number of intervals. Each of the following \(n\) lines contains two space-separated integers \(p_i\) and \(q_i\) representing an interval \([p_i, q_i]\).

It is guaranteed that the input values are such that a simple iterative solution over the range \([\min_i{p_i}, \max_i{q_i}]\) is feasible.

outputFormat

Output a single integer which is the result of the sum modulo \(998244353\).

sample

1
1 3

6