zhtobu3232的线段树

$zhtobu3232$发现了一道线段树题,在$30s$后$zhtobu3232$敲出了一份线段树并且ac了这题 当然，这是$zhtobu3232$刚刚学oi时候的事情了，现在的他只需$1s$就可以敲出一份完美的线段树板子 现在$ztb$想要重温一下他之前切过的水题,不过他的笔记本电脑年代有些久远，导致内存条损坏了很多，从而线段树也开始损坏了，现在他不关心当年敲了什么水题而只关心这个线段树可以表示出多少合法的区间，请你计算出这个数字并对$998244353$取模 顺便说一句$ztb$认为这个问题比线段树简单多了，因为线段树的节点少了,所以维护的信息也少了，他已经用$1ms$敲好了$std$,接下来就等着你帮他验题了

我们定义一颗长度为n的线段树是这样的算法流程执行build(0,n)后建出的二叉树 (注意这里的线段树应该和大家平常写的没什么区别(除了区间是左开右闭表示的以外)，会线段树的可以忽略) ```C node build (l,r) { node p=newnode();p.l=l+1;p.r=r; if(r-l==1)return p; mid=(l+r)/2; node.leftson=build(l,mid); node.rightson=build(mid,r); return p; } ``` 而我们定义一个区间$(l,r)$在线段树上的**拆分**是将这个区间表示为线段树上若干个节点的集合，满足这些节点对应的区间不相交,不嵌套,这些区间的并集恰好是$(l,r)$，并且没有两个节点是兄弟关系 拆分的伪代码如下 ```C void solve(l,r,dl,dr) { if(dl==l&&dr==r){S.push(node(l+1,r));return;} mid=(l+r)/2; if(dl<mid)solve(l,mid,dl,min(dr,mid)); if(mid<dr)solve(mid,r,max(dl,mid),dr); } ``` 当我们执行完$solve(0,n,l-1,r)$之后得到的S集合就是区间$(l,r)$在$(1,n)$这颗线段树上的**拆分**了 (换句话说就是你平时写线段树时将一个区间拆成$O(logn)$个区间的操作) 现在我们给出了m个区间$(l,r)$，这些区间在线段树$(1,n)$上拆分出来的节点都是非法节点，换句话说这些节点都不可以使用了 现在请你计算有多少个区间$(l,r)$是合法的，满足两个限制条件 第一：$1 \leq l \leq r \leq n$ 第二：这个区间在线段树$(1,n)$上的拆分不含有非法的节点 答案对998244353取模

**为了避免您被题意杀，请务必按照题目中给出的左开右闭法建线段树，采用其他的建树方式可能导致线段树的形态和std中的线段树不符导致wa** 第一行两个整数n,m表示线段树的长度和区间个数 接下来m行每行两个整数l,r,表示$(l,r)$这个区间在线段树上拆分出的节点全部为非法节点

仅一行一个整数，表示所有合法的区间个数对998244353取模之后的值

20 5
11 12
14 20
6 12
8 13
10 19

67

1,2,3,4,5,6,7测试点的分数全部为1分 对于测试点1,2 $$n \leq 1000,m\leq 100$$ 对于测试点3,4 $$n \leq 100000,m \leq 5000$$ 对于测试点5,6,7 $$n \leq 10^7,m \leq 10^5$$ 对于所有数据 $$1 \leq n \leq 10^{14}$$ $$1 \leq m \leq 10^5$$ $$1 \leq l \leq r \leq n$$