Background

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.

Problem 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