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 [li,ri] independently and uniformly, then he walks x meters to east. Now he has n ranges [l1,r1],[l2,r2]...[ln,rn], He wants to know the expected distance to origin. If answer is a fraction pq, output an integer 0≤s<998244353 so that p≡sq (mod 998244353).
Input
An integer n in the first line. 1≤n≤15 The following n lines, each contain two integers li,ri. (−106≤li≤ri≤106)
Output
Output the expected distance to origin in a line, modulo 998244353.