#P18356. Under the Epilogue

Under the Epilogue

Under the Epilogue

输入:标准输入
输出:标准输出

题目描述

有 nn 个位置,编号为 1,2,…,n1,2,\ldots,n。位置 ii 有两个参数 ai,bia_i,b_i,满足 ai≤i≤bia_i\le i\le b_i。每次位于 ii 时,可以移动到任意满足 ai≤j≤bia_i\le j\le b_i 的位置 jj。

你可以任选一个位置 uu 作为起点,移动任意多步后回到 uu。也可以一步都不移动,直接停在 uu。

令 SS 为这次从 uu 出发并回到 uu 的过程中,至少经过一次的所有位置组成的集合。起点也属于 SS。位置和边都允许重复经过。

求总共可以得到多少个不同的集合 SS,答案对 998244353998244353 取模。只按集合是否相同计数;起点、移动顺序或移动次数不同,但集合相同的,只计一次。

输入格式

第一行包含一个整数 nn。

接下来 nn 行,第 ii 行包含两个整数 ai,bia_i,b_i。

输出格式

输出一行一个整数,表示不同集合 SS 的数量对 998244353998244353 取模的结果。

数据范围

  • 1≤n≤501\le n\le50;
  • 对于所有 1≤i≤n1\le i\le n,1≤ai≤i≤bi≤n1\le a_i\le i\le b_i\le n。

本题只有一个测试用例,没有测试用例数 TT。

样例输入 1

5
1 2
2 5
3 4
2 5
4 5

样例输出 1

12