Segment Tree Interval Splitting

We are given an integer n and a segment tree built on the interval [1, n] (constructed by invoking build(0, n) as shown below). In our segment tree each node is associated with an interval: when we call build(l, r) the node is assigned the interval [l+1, r] (note the left‐open, right-closed convention aside from the shift by one).

node build(l, r) {
    node p = newnode();
    p.l = l+1; p.r = r;
    if(r-l==1) return p;
    mid = (l+r)/2;
    p.left = build(l, mid);
    p.right = build(mid, r);
    return p;
}

For any interval (l, r) with 1 ≤ l ≤ r ≤ n, we define its splitting as the unique set of nodes in the segment tree (found via the procedure below) whose intervals are disjoint, do not contain one another and their union is exactly (l, r). Moreover, no two nodes in the splitting are siblings. The pseudocode to obtain the splitting 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);
}

In other words, when we call solve(0, n, l-1, r) the resulting set S is the canonical splitting of (l, r) on the segment tree built on [1, n].

Now, you are given m intervals. For each of these intervals (l, r), all nodes obtained from its splitting (i.e. by running solve(0, n, l-1, r)) are marked illegal and cannot be used.

Your task is to count the number of intervals (l, r) (with 1 ≤ l ≤ r ≤ n) that are legal, i.e. the canonical splitting of (l, r) on the segment tree does not contain any illegal node. Output your answer modulo 998244353.

Input Format:

• The first line contains two integers n and m.
• The next m lines each contain two integers l and r representing an interval whose splitting nodes are marked illegal.

Output Format:

• Output a single integer: the number of legal intervals (l, r) modulo 998244353.

Note: The splitting of an interval (l, r) is obtained by the recursive procedure solve(0, n, l-1, r) on the segment tree built on [1, n].

inputFormat

The first line contains two integers n (the size of the segment tree) and m (the number of illegal intervals).

Each of the next m lines contains two integers l and r, representing an interval whose splitting nodes are illegal.

outputFormat

Output a single integer: the number of legal intervals (l, r) with 1 ≤ l ≤ r ≤ n such that the canonical splitting of (l, r) (obtained by running solve(0, n, l-1, r)) contains no illegal node, modulo 998244353.

sample

3 1
2 3

5

</p>