P11754 [COCI 2024/2025 #5] 绘图 / Crtež

译自 [COCI 2024/2025 #5](https://hsin.hr/coci/) 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$。**

无

无

#### 样例解释 样例 $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$。 | 子任务编号 | $n\le$ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 10^3$ | A | $ 20 $ | | $ 2 $ | $10^6$ | | $ 55 $ | | $ 3 $ | $10^{18}$ | | $ 45 $ | 特殊性质 A：$q\le 10^3$。