题目描述

定义一个合法括号序列为仅由 ( 和 ) 构成的字符串且：

• 空串 S 是一个合法括号序列。

• 如果 A 是一个合法序列，那么 (A) 也是合法括号序列。

• 如果 A,B 都是合法括号序列，那么 AB 也是合法括号序列。

例如 (())() 是合法括号序列，而 )()) 不是。

定义一个长度为 $2n$ 的合法括号序列是优秀的，当且仅当其满足：对于从左到右的第 $i$ 个左括号，与其匹配的右括号和这个左括号之间的距离在$[L_i , R_i ]$ 之间。

给出 n 和 $L_{1···n}$, $R_{1···n}$，请求出有多少长度为 $2n$ 的优秀的合法括号序列。由于答案可能很大，你只需要回答其对$998244353$ 取模后的结果。

你可以通过阅读样例解释以更好地理解题意。

输入格式

从文件 $bracket.in$ 中读入数据。 第一行一个正整数 $n$。 接下来 $n$ 行，第 i 行两个整数 $L_i , R_i$。

输出格式

输出到文件 $bracket.out$ 中。 一行一个整数表示答案。

样例 $1$ 输入

3
1 5
1 1
1 5

样例 $1$输出

3

样例 $1$ 解释

三种优秀的合法括号序列分别为：(())()，(()())和()()()

对于第一种优秀的合法括号序列，第一个左括号位于位置 $1$，与其匹配的右括号位于 位置 $4$，距离 $d = 4 − 1 = 3$，满足 $L_1 = 1 ≤ d ≤ R_1 = 5$。

样例 $2,3$

见$/{ex\_bracket2.in},/ex\_bracket3.in 与 /ex\_bracket2.out,/ex\_bracket3.out$。

测试点约束

对于所有测试点，$1 ≤ n ≤ 700，1 ≤ L_i , R_i ≤ 2n − 1$。

每个测试点的具体限制见下表：