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-----

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-----

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)$.


-----Examples-----
Input
3
1 2
1 2
1 2

Output
499122177

Input
2
42 1337
13 420

Output
578894053

Input
2
1 1
0 0

Output
1

Input
2
1 1
1 1

Output
1



-----Note-----

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

Difficulty: interview

Starter code:

Solutions:
from bisect import bisect_left

M = 998244353

def pw(x, y):
    if y == 0:
        return 1
    res = pw(x, y//2)
    res = res * res % M
    if y % 2 == 1:
        res = res * x % M
    return res

def cal(x, y):
    y += x - 1
    res = 1
    for i in range(1, x + 1):
        res = res * (y - i + 1)
        res = res * pw(i, M - 2) % M
    return res % M

n = int(input())
a = []
b = []
res = 1
for i in range(n):
    a.append(list(map(int, input().split())))
    res = res * (a[-1][1] + 1 - a[-1][0]) % M
    b.append(a[-1][0])
    b.append(a[-1][1] + 1)
    b = set(b)
    b = sorted(list(b))

g = [b[i + 1] - b[i] for i in range(len(b) - 1)]

for i in range(n):
    a[i][0] = bisect_left(b, a[i][0])
    a[i][1] = bisect_left(b, a[i][1] + 1)

a = a[::-1]

f = [[0 for _ in range(len(b))] for __ in range(n)]

for i in range(a[0][0], len(b)):
    if i == 0:
        f[0][i] = g[i]
    else:
        if i < a[0][1]:
            f[0][i] = (f[0][i - 1] + g[i]) % M
        else:
            f[0][i] = f[0][i - 1]
        
for i in range(1, n):
    for j in range(a[i][0], len(b)):
        if j > 0:
            f[i][j] = f[i][j - 1]
        if j < a[i][1]:
            for k in range(i, -1, -1):
                if a[k][1] <= j or j < a[k][0]:
                    break
                if k == 0 or j != 0:
                    tmp = cal(i - k + 1, g[j])
                    if k > 0:
                        f[i][j] += f[k - 1][j - 1] * tmp % M
                    else:
                        f[i][j] += tmp
                    f[i][j] %= M
                    
#print(f)
#print(f[n - 1][len(b) - 1], res)
print(f[n - 1][len(b) - 1] * pw(res, M - 2) % M)


from bisect import bisect_left

M = 998244353

def pw(x, y):
    if y == 0:
        return 1
    res = pw(x, y//2)
    res = res * res % M
    if y % 2 == 1:
        res = res * x % M
    return res

def cal(x, y):
    y += x - 1
    res = 1
    for i in range(1, x + 1):
        res = res * (y - i + 1)
        res = res * pw(i, M - 2) % M
    return res % M

n = int(input())
a = []
b = []
res = 1
for i in range(n):
    a.append(list(map(int, input().split())))
    res = res * (a[-1][1] + 1 - a[-1][0]) % M
    b.append(a[-1][0])
    b.append(a[-1][1] + 1)
    b = set(b)
    b = sorted(list(b))

g = [b[i + 1] - b[i] for i in range(len(b) - 1)]

for i in range(n):
    a[i][0] = bisect_left(b, a[i][0])
    a[i][1] = bisect_left(b, a[i][1] + 1)

a = a[::-1]

f = [[0 for _ in range(len(b))] for __ in range(n)]

for i in range(a[0][0], len(b)):
    if i == 0:
        f[0][i] = g[i]
    else:
        if i < a[0][1]:
            f[0][i] = (f[0][i - 1] + g[i]) % M
        else:
            f[0][i] = f[0][i - 1]
        
for i in range(1, n):
    for j in range(a[i][0], len(b)):
        if j > 0:
            f[i][j] = f[i][j - 1]
        if j < a[i][1]:
            for k in range(i, -1, -1):
                if a[k][1] <= j or j < a[k][0]:
                    break
                if k == 0 or j != 0:
                    tmp = cal(i - k + 1, g[j])
                    if k > 0:
                        f[i][j] += f[k - 1][j - 1] * tmp % M
                    else:
                        f[i][j] += tmp
                    f[i][j] %= M
                    
#print(f)
#print(f[n - 1][len(b) - 1], res)
print(f[n - 1][len(b) - 1] * pw(res, M - 2) % M)


import sys
from itertools import chain
readline = sys.stdin.readline

MOD = 998244353
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


N = int(readline())
LR = [tuple(map(int, readline().split())) for _ in range(N)]
LR = [(a-1, b) for a, b in LR]
LR2 = LR[:]
ml = LR[-1][0]
res = 0
for i in range(N-2, -1, -1):
    l, r = LR[i]
    if r <= ml:
        break
    l = max(ml, l)
    ml = l
    LR[i] = (l, r)
else:
    Z = list(chain(*LR))
    Z2, Dc = compress(Z)
    
    NN = len(Z2)
    seglen = [0] + [n - p for p, n in zip(Z2, Z2[1:])]
    
    hc = [[0]*(N+3) for _ in range(NN)]
    for j in range(NN):
        hc[j][0] = 1
        for k in range(1, N+3):
            hc[j][k] = hc[j][k-1]*pow(k, MOD-2, MOD)*(seglen[j]-1+k)%MOD

    mask = [[[True]*NN]]

    dp = [[[0]*(N+1) for _ in range(NN+1)] for _ in range(N+1)]
    Dp = [[1]*(NN+1)] + [[0]*(NN+1) for _ in range(N)]
    for i in range(1, N+1):
        mask2 = [False]*NN
        l, r = LR[i-1]
        dl, dr = Dc[l], Dc[r]
        for j in range(dr, dl, -1):
            mask2[j] = True
        mm = [[m1&m2 for m1, m2 in zip(mask[-1][idx], mask2)] for idx in range(i)] + [mask2]
        mask.append(mm)
        for j in range(NN):
            for k in range(1, i+1):
                if mask[i][i-k+1][j]:
                    dp[i][j][k] = Dp[i-k][j+1]*hc[j][k]%MOD
        
        for j in range(NN-1, -1, -1):
            res = Dp[i][j+1]
            if dl < j <= dr:
                for k in range(1, i+1):        
                    res = (res + dp[i][j][k])%MOD
            Dp[i][j] = res
    
    res = Dp[N][0]
    for l, r in LR2:
        res = res*(pow(r-l, MOD-2, MOD))%MOD
print(res)



from bisect import bisect_left
 
M = 998244353
 
def pw(x, y):
    if y == 0:
        return 1
    res = pw(x, y//2)
    res = res * res % M
    if y % 2 == 1:
        res = res * x % M
    return res
 
def cal(x, y):
    y += x - 1
    res = 1
    for i in range(1, x + 1):
        res = res * (y - i + 1)
        res = res * pw(i, M - 2) % M
    return res % M
 
n = int(input())
a = []
b = []
res = 1
for i in range(n):
    a.append(list(map(int, input().split())))
    res = res * (a[-1][1] + 1 - a[-1][0]) % M
    b.append(a[-1][0])
    b.append(a[-1][1] + 1)
    b = set(b)
    b = sorted(list(b))
 
g = [b[i + 1] - b[i] for i in range(len(b) - 1)]
 
for i in range(n):
    a[i][0] = bisect_left(b, a[i][0])
    a[i][1] = bisect_left(b, a[i][1] + 1)
 
a = a[::-1]
 
f = [[0 for _ in range(len(b))] for __ in range(n)]
 
for i in range(a[0][0], len(b)):
    if i == 0:
        f[0][i] = g[i]
    else:
        if i < a[0][1]:
            f[0][i] = (f[0][i - 1] + g[i]) % M
        else:
            f[0][i] = f[0][i - 1]
        
for i in range(1, n):
    for j in range(a[i][0], len(b)):
        if j > 0:
            f[i][j] = f[i][j - 1]
        if j < a[i][1]:
            for k in range(i, -1, -1):
                if a[k][1] <= j or j < a[k][0]:
                    break
                if k == 0 or j != 0:
                    tmp = cal(i - k + 1, g[j])
                    if k > 0:
                        f[i][j] += f[k - 1][j - 1] * tmp % M
                    else:
                        f[i][j] += tmp
                    f[i][j] %= M
                    
#print(f)
#print(f[n - 1][len(b) - 1], res)
print(f[n - 1][len(b) - 1] * pw(res, M - 2) % M)

import sys
input = sys.stdin.readline

mod=998244353
n=int(input())
LR=[list(map(int,input().split())) for i in range(n)]
RMIN=1<<31

ALL=1
for l,r in LR:
    ALL=ALL*pow(r-l+1,mod-2,mod)%mod

for i in range(n):
    if LR[i][1]>RMIN:
        LR[i][1]=RMIN
    RMIN=min(RMIN,LR[i][1])

LMAX=-1
for i in range(n-1,-1,-1):
    if LR[i][0]<LMAX:
        LR[i][0]=LMAX
    LMAX=max(LMAX,LR[i][0])

compression=[]
for l,r in LR:
    compression.append(l)
    compression.append(r+1)

compression=sorted(set(compression))
co_dict={a:ind for ind,a in enumerate(compression)}

LEN=len(compression)-1

if LEN==0:
    print(0)
    return

DP=[[0]*LEN for i in range(n)]

for i in range(co_dict[LR[0][0]],co_dict[LR[0][1]+1]):
    x=compression[i+1]-compression[i]
    now=x
    #print(i,x)
    for j in range(n):
        if LR[j][0]<=compression[i] and LR[j][1]+1>=compression[i+1]:
            DP[j][i]=now
        else:
            break
        now=now*(x+j+1)*pow(j+2,mod-2,mod)%mod

#print(DP)

for i in range(1,n):
    SUM=DP[i-1][LEN-1]
    #print(DP)
    for j in range(LEN-2,-1,-1):
        if LR[i][0]<=compression[j] and LR[i][1]+1>=compression[j+1]:
            x=SUM*(compression[j+1]-compression[j])%mod
            now=x
            t=compression[j+1]-compression[j]
            #print(x,t)

            for k in range(i,n):
                
                if LR[k][0]<=compression[j] and LR[k][1]+1>=compression[j+1]:
                    DP[k][j]=(DP[k][j]+now)%mod
                else:
                    break
                now=now*(t+k-i+1)*pow(k-i+2,mod-2,mod)%mod
                
        
        SUM+=DP[i-1][j]

print(sum(DP[-1])*ALL%mod)

        
        
    


import sys
input = sys.stdin.readline

mod=998244353
n=int(input())
LR=[list(map(int,input().split())) for i in range(n)]
RMIN=1<<31

ALL=1
for l,r in LR:
    ALL=ALL*pow(r-l+1,mod-2,mod)%mod

for i in range(n):
    if LR[i][1]>RMIN:
        LR[i][1]=RMIN
    RMIN=min(RMIN,LR[i][1])

LMAX=-1
for i in range(n-1,-1,-1):
    if LR[i][0]<LMAX:
        LR[i][0]=LMAX
    LMAX=max(LMAX,LR[i][0])

compression=[]
for l,r in LR:
    compression.append(l)
    compression.append(r+1)

compression=sorted(set(compression))
co_dict={a:ind for ind,a in enumerate(compression)}

LEN=len(compression)-1

if LEN==0:
    print(0)
    return

DP=[[0]*LEN for i in range(n)]

for i in range(co_dict[LR[0][0]],co_dict[LR[0][1]+1]):
    x=compression[i+1]-compression[i]
    now=x
    #print(i,x)
    for j in range(n):
        if LR[j][0]<=compression[i] and LR[j][1]+1>=compression[i+1]:
            DP[j][i]=now
        else:
            break
        now=now*(x+j+1)*pow(j+2,mod-2,mod)%mod

#print(DP)

for i in range(1,n):
    SUM=DP[i-1][LEN-1]
    #print(DP)
    for j in range(LEN-2,-1,-1):
        if LR[i][0]<=compression[j] and LR[i][1]+1>=compression[j+1]:
            x=SUM*(compression[j+1]-compression[j])%mod
            now=x
            t=compression[j+1]-compression[j]
            #print(x,t)

            for k in range(i,n):
                
                if LR[k][0]<=compression[j] and LR[k][1]+1>=compression[j+1]:
                    DP[k][j]=(DP[k][j]+now)%mod
                else:
                    break
                now=now*(t+k-i+1)*pow(k-i+2,mod-2,mod)%mod
                
        
        SUM+=DP[i-1][j]

print(sum(DP[-1])*ALL%mod)