Cho ~n~ đoạn có hai đầu mút nguyên ~[L_i, R_i] (0 \leq L_i \leq R_i \leq 10^{9})~. Từ mỗi đoạn lấy ngẫu nhiên ra một số thực ~L_i \leq x_i \leq R_i~.

Gọi ~E~ là giá trị kỳ vọng của ~max(x_i)~. Tính ~E~ modulo ~998244353~.

Input

Dòng đầu tiên chứa số nguyên dương ~n (n \leq 2000)~ là số bộ dữ liệu của test.

Mỗi dòng trong ~n~ dòng tiếp theo chứa hai số nguyên ~L_i~ và ~R_i~.

Output

In ra một số nguyên duy nhất là kết quả của bài toán ~E~ modulo ~998244353~.

Sample Input 1

1
1 2

Sample Output 1

499122178

Sample Input 2

2
1 2
1 2

Sample Output 2

665496237

Notes

Đáp án của Sample Input 1 là 1.5 (modulo ~998244353~).