给定一个长度为 $N$ 的序列，初始时全为 $0$。在游戏过程中，我们通过一系列操作对序列中的位置进行染色，并且可以在任意操作后停止。

第 $X$ 次染色操作的步骤如下：

• 选择一个包含 $0$ 的位置。
• 决定执行以下操作之一：
  • 将选定位置染为 $-1$。
  • 将选定位置染为颜色 $X$，并继续向左对相邻位置染上颜色 $X$。当我们遇到一个值不为 $0$ 的位置（该位置不染色）或者超出序列边界时，停止染色。

如果两个游戏最终得到的序列可以通过重命名大于 $0$ 的颜色来相互转化，则称这两个游戏是等价的。即存在一个双射映射，满足：

• 映射后的颜色仍然大于 $0$。
• 每种颜色对应唯一的新标签。
• 映射后，两个序列完全相同。

等价游戏的一个例子：

• $[1, 1, -1, 2, -1, 3, 0]$
• $[3, 3, -1, 1, -1, 2, 0]$

因为存在一种颜色映射（颜色 $1$ 映射为 $3$，颜色 $2$ 映射为 $1$，颜色 $3$ 映射为 $2$），使得上述所有条件均满足。

给定 $Q$ 次更新，每次更新将序列区间 $[L, R]$ 内所有的 $0$ 变为 $-1$，所有的 $-1$ 变为 $0$。

在每次更新后，计算 $K$ 的值，即在任意次数的操作下，能够进行的不同游戏数量，使得没有两个游戏是等价的。由于 $K$ 非常大，请输出结果对 $10^9 + 7$ 取模后的值。

输入格式

第一行包含两个自然数 $N, Q$ ($1 \le N \le 10^{18}, 1 \le Q \le 10^5$)，分别表示序列的长度和更新次数。

接下来的 $Q$ 行，每行包含两个自然数 $L$ 和 $R$ ($1 \le L, R \le N$)，表示题目描述中的更新区间。

输出格式

在 $Q$ 行中，第 $i$ 行输出每次更新后 $K$ 对 $10^9 + 7$ 取模的结果。

子任务

样例

输入格式 1

1 2
1 1
1 1

输出格式 1

1
3

说明

第一次更新后，序列变为 $[-1]$。我们无法对其进行任何操作，因此最多能进行 $1$ 种游戏。第二次更新后，序列变为 $[0]$。从序列 $[0]$ 出发，使用题目描述的操作，我们可以得到序列 $[0], [1]$ 和 $[-1]$。我们观察到这些序列中没有一对是等价的，因此最多能进行 $3$ 种游戏。

输入格式 2

3 2
2 2
1 3

输出格式 2

9
3

输入格式 3

57 2
13 39
6 42

输出格式 3

130653412
804077942