题目解析

题目名称：AT_abc453_e [ABC453E] Team Division
难度：普及+/提高
算法：容斥 + 差分
来源：AtCoder ABC453E

题目描述

将选手1、选手2、……、选手N这N个人分成两个可区分的队伍A和B，要求满足以下所有条件：

1. 每个队伍由至少1名选手组成。
2. 每名选手恰好属于队伍A或队伍B中的其中一个。
3. 选手i所属的队伍中，人数必须在$L_i$到$R_i$之间。

请计算满足条件的分组方式有多少种，并输出该数值除以$998244353$的余数。
注意：如果存在某位选手在两种分组方式中属于不同的队伍，则这两种分组方式被视为不同。

输入格式

N L_1 R_1 L_2 R_2 ⋮ L_N R_N

输出格式

输出满足条件的划分方式的总数对$998244353$取模的结果。

输入输出样例

样例1

输入：

3 1 1 1 2 2 2

输出：

2

样例说明：两种合法分法

• 选手1→A，选手2→B，选手3→B
• 选手1→B，选手2→A，选手3→A

样例2

输入：

7 6 1 5 1 5 2 5 1 3 3 5 2 5

输出：

30

限制条