Absolute

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.

Sample Input

2

-2 3

-2 1

Sample Output

199648872

Source

2018 Multi-University Training Contest 2

https://acm.hdu.edu.cn/showproblem.php?pid=6309