Polycarp 玩一个(又一个!)战略电脑游戏。在这款游戏中,他领导着一支雇佣兵军队。
坡旅甲想要集结他的军队来执行任务。有$$$n$$$雇佣兵可供雇佣,军队应该由其中的某些子集组成。
如果所选雇佣兵的最终数量不小于$$$l_i$$$(否则他认为任务注定失败)并且不大于$$$r_i$$$(他不想与太多其他雇佣兵分享奖杯),则可以选择第$$$i$$$个雇佣兵。此外,$$$m$$$ 的雇佣兵彼此憎恨,不能被选中执行同一任务。
Polycarp 需要考虑多少个非空子集?换句话说,计算非空雇佣兵子集的数量,使得该子集的大小对于每个选定的雇佣兵属于$$$[l_i, r_i]$$$,并且该子集中不存在互相仇恨的两个雇佣兵。
答案可能很大,因此请以 $$$998244353$$$ 为模进行计算。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$0 \le m \le \min(20, \dfrac{n(n-1)}{2})$$$) — 雇佣兵的数量和相互仇恨的雇佣兵对的数量。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。
接下来是 $$$m$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i < b_i \le n$$$) 表示雇佣兵 $$$a_i$$$ 和 $$$b_i$$$ 互相仇恨。此列表中没有两个相等的对。
输出
打印一个整数 — 满足约束的非空子集的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
3 0 1 1 2 3 1 3
输出 #1
3
输入 #2
3 1 1 1 2 3 1 3 2 3
输出 #2
2