Problem Description

Winter is here at the North and the White Walkers are close. There's a young Night Watch standing on the Wall.
The young Night Watch has created a method to keep his body warm. Every time he generate a random rational number x in range $[l_i, r_i]$ independently and uniformly, then he walks x meters to east.
Now he has n ranges $[l_1, r_1], [l_2, r_2] ... [l_n, r_n]$, He wants to know the expected distance to origin. If answer is a fraction $\frac{p}{q}$, output an integer $0 \leq s < 998244353$ so that $p \equiv sq~(mod~998244353)$.

Input

An integer n in the first line. $1 \leq n \leq 15$
The following n lines, each contain two integers $l_i, r_i$. $(-10^6 \leq l_i \leq r_i \leq 10^6)$

Output

Output the expected distance to origin in a line, modulo 998244353.

2
-2 3
-2 1

199648872