背景

译自 COCI 2024/2025 #5 T4。$\texttt{2s,0.5G}$。满分为 $120$。

赛时公告：$a_i$ 初值为 $0$。

题目描述

考虑一个长度为 $n$ 的整数序列 $a_1,\ldots,a_n$，初始时 $a_i\in \{-1,0\}$。

你可以按照如下的步骤操作任意多次（包括零次）：

• 令这是第 $x$ 次操作。首先选择 $i$ 满足 $1\le i\le n$，且 $a_i=0$。（如果不存在，则无法继续操作）
• 从如下的操作中二选一：
  • 令 $a_i\gets -1$，然后终止本次操作。
  • 令 $a_i\gets x$。重复执行以下操作，直到 $i=1$ 或 $a_{i-1}\neq 0$：
    • 令 $i\gets i-1$，然后令 $a_{i}\gets x$。

操作完后会得到若干个结果序列 $a$。

我们称两个序列 $a,b$ 等价，当且仅当，能够重标号 $a$ 序列中 $>0$ 的元素，使得重标号后这两个序列相等。

例如，$[1,1,-1,5,1,0]$ 和 $[2,2,-1,6,2,0]$ 等价。

更为精确地说，如果能构造一个双射 $f: \{-1,0,\ldots\}\to \{-1,0,\ldots\}$，满足：

• $f(-1)=-1$，$f(0)=0$；
• 对于 $i\gt 0$，$f(i)\gt 0$；
• $[f(a_1),f(a_2),\ldots,f(a_n)]=[b_1,b_2,\ldots,b_n]$。

那我们就说，$a$ 和 $b$ 等价。

现在有 $q$ 个操作。每个操作给定 $l,r$，将 $a_l,a_{l+1},\ldots,a_r$ 中的 $0$ 同时替换成 $-1$，$-1$ 同时替换成 $0$。

每次操作后，求出以当前的 $a$ 序列为起始序列，操作得到的互不等价的结果序列的数量模 $(10^9+7)$ 后的结果。

没有进行任何操作之前，$a_i=0$。

输入格式

第一行，正整数 $n,q$。

接下来 $q$ 行，每行两个正整数 $l,r$，描述一次操作。

输出格式

输出 $q$ 行，第 $i$ 行一个非负整数，表示第 $i$ 次操作得到的互不等价的序列数量模 $(10^9+7)$ 后的结果。

1 2
1 1
1 1

1
3

3 2
2 2
1 3

9
3

57 2
13 39
6 42

130653412
804077942

提示

样例解释

样例 $1$ 解释：

第一次操作后，$a=[-1]$。无法操作。互不等价的序列只有 $[-1]$。

第二次操作后，$a=[0]$。互不等价的序列有 $[0],[1],[-1]$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 10^{18}$；
• $1\le q\le 10^5$；
• $1\le l\le r\le n$。

特殊性质 A：$q\le 10^3$。