Description

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.

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:

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);
}

After executing solve(0,n,l-1,r), the set $S$ obtained is exactly the decomposition of interval $(l,r)$ on the segment tree $(1,n)$. In other words, it is the operation you usually do in a segment tree where you split an interval into $O(\log n)$ intervals.

Now we are given $m$ intervals $(l,r)$. All nodes produced by decomposing these intervals on the segment tree $(1,n)$ are illegal nodes. In other words, these nodes cannot be used.

Now please compute how many intervals $(l,r)$ are valid, satisfying the following two constraints:

1. $1 \leq l \leq r \leq n$.
2. The decomposition of this interval on the segment tree $(1,n)$ does not contain any illegal nodes.

Output the answer modulo $998244353$.

Input Format

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 Format

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

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

67

Hint

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