P5111 zhtobu3232’s Segment Tree

zhtobu3232 found a segment tree problem. After 30 seconds, zhtobu3232 typed out a segment tree and got AC on it. Of course, that was when zhtobu3232 had just started learning OI. Now he only needs 1 second to type out a perfect segment tree template. Now ztb wants to relive those easy problems he solved before. But his laptop is quite old, and many memory sticks have been damaged, so the segment tree has also started to break. Now he does not care what easy problem he coded back then; he only cares about how many valid intervals this segment tree can represent. Please compute this number and take it modulo $998244353$. By the way, ztb thinks this problem is much simpler than a segment tree, because the segment tree has fewer nodes, so there is less information to maintain. He has already typed the std in 1 ms, and now he is waiting for you to help validate the problem.

We define a segment tree of length $n$ as the binary tree built by executing `build(0,n)` in the following algorithm. Note that this segment tree should be almost the same as the one everyone usually writes (except that intervals are represented as left-open right-closed). If you know segment trees, you may ignore this note. ```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; } ``` We define the **decomposition** of an interval $(l,r)$ on the segment tree as representing this interval as a set of several nodes on the segment tree, such that the intervals corresponding to these nodes are non-overlapping, not nested, their union is exactly $(l,r)$, and no two nodes are siblings. The pseudo-code for decomposition is: ```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

**To avoid being misled by the statement, you must build the segment tree using the left-open right-closed convention described in the problem. Using other building methods may cause the segment tree shape to differ from the one in std, leading to WA.** The first line contains two integers $n,m$, representing the length of the segment tree and the number of intervals. The next $m$ lines each contain two integers $l,r$, meaning that all nodes produced by decomposing the interval $(l,r)$ on the segment tree are illegal nodes.

Output one integer in a single line: the number of all valid intervals modulo $998244353$.

The scores of test points $1,2,3,4,5,6,7$ are all $1$ point. For test points $1,2$, $n \leq 1000,m \leq 100$. For test points $3,4$, $n \leq 100000,m \leq 5000$. For test points $5,6,7$, $n \leq 10^7,m \leq 10^5$. For all testdata, $1 \leq n \leq 10^{14}$, $1 \leq m \leq 10^5$, $1 \leq l \leq r \leq n$. Translated by ChatGPT 5