AT_abc453_e [ABC453E] Team Division
题目描述
将选手 $1$、选手 $2$、$\ldots$、选手 $N$ 这 $N$ 个人分成两个(可区分的)队伍 $A$ 和 $B$,要求满足以下所有条件。
- 每个队伍由至少 $1$ 名选手组成。
- 每名选手恰好属于队伍 $A$ 或队伍 $B$ 中的其中一个。
- 选手 $i$ 所属的队伍中,人数必须在 $L_i$ 到 $R_i$ 之间。
请计算满足条件的分组方式有多少种,并输出该数值除以 $998244353$ 的余数。
注意,如果存在某位选手在两种分组方式中属于不同的队伍,则这两种分组方式被视为不同。
输入格式
输入以以下形式从标准输入中给出。
> $ N $ \
> $ L_1 $ $ R_1 $\
> $ L_2 $ $ R_2 $\
> $ \vdots $\
> $ L_N $ $ R_N $
输出格式
输出满足条件的划分方式的总数除以 $998244353$ 的余数。
说明/提示
### 示例说明 1
以下两种分法满足条件。
- 运动员 $1$:队伍 $A$,运动员 $2$:队伍 $B$,运动员 $3$:队伍 $B$。
- 运动员 $1$:队伍 $B$,运动员 $2$:队伍 $A$,运动员 $3$:队伍 $A$。
由于 $2$ 除以 $998244353$ 的余数是 $2$,因此输出 $2$。
### 示例说明 2
满足条件的分法共有 $30$ 种。
### 限制条件
- $2\leq N\leq 2\times 10^5$。
- $1\leq L_i\leq R_i\leq N-1$。
- 所有输入均为整数。