P14523 【MX-S11-T4】Ice Drop

[Ice Drop - Aqu3ra / 鏡音レン / MORE MORE JUMP！](https://www.bilibili.com/video/BV1p64y1q7vM) > このセカイを回す　唯一の魔法 > > 让这世界回转的　唯一的魔法

定义一个正整数序列是好的，当且仅当对任意正整数 $k$，若序列中存在 $k$ 的倍数，则所有 $k$ 的倍数在序列中的位置连续。例如 $[1, 2, 6, 3]$ 是好的，而 $[1, 2, 3, 6]$ 不是好的，因为该序列中 $2$ 的倍数在序列中的位置分别是 $2, 4$，并不是连续的一段。 对于一个长度为 $m$ 的正整数序列 $b$，定义 $f(b)$ 为满足以下条件的**好的**正整数序列 $b'$ 的数量： - $b' = [b'_1, \ldots, b'_m]$ 的长度为 $m$； - 若 $b_i > 1$，则 $b'_i = b_i$（$1 \le i \le m$）。 - $\operatorname{LCM}(b_1, b_2, \dots, b_m) = \operatorname{LCM}(b'_1, b'_2, \dots, b'_m)$。 爱莉有一个长度为 $n$ 的正整数序列 $a_1, \ldots, a_n$，她向你提出了 $q$ 个问题，每次给出两个数 $l, r$，你要求出 $\sum_{x = l}^r \sum_{y = x}^r f(a[x, y])$ 的值对 $10^9 + 7$ 取模的结果。 注：$a[x, y]$ 表示序列 $a$ 的子串 $[a_x, \ldots, a_y]$。$\operatorname{LCM}$ 表示若干个正整数的最小公倍数。

第一行，两个正整数 $n, q$。 第二行，$n$ 个正整数 $a_1, \ldots, a_n$。 接下来 $q$ 行，每行两个正整数 $l, r$，表示一个问题。

输出 $q$ 行，每行一个非负整数，第 $i$ 行表示第 $i$ 个问题的答案对 $10^9 + 7$ 取模后的值。

**【样例解释 #1】** 对于第一个样例： - 有 $f(a[2, 4]) = 4$，对应的好序列分别为 $[1, 2, 1], [1, 2, 2], [2, 2, 1], [2, 2, 2]$。 - 有 $f(a[6, 9]) = 2$，对应的好序列分别为 $[6, 3, 3, 5], [6, 6, 3, 5]$。 **【样例 #4】** 见选手目录下的 $\textbf{\textit{icedrop/icedrop4.in}}$ 与 $\textbf{\textit{icedrop/icedrop4.ans}}$。 该样例满足测试点 $1, 2$ 的约束条件。 **【样例 #5】** 见选手目录下的 $\textbf{\textit{icedrop/icedrop5.in}}$ 与 $\textbf{\textit{icedrop/icedrop5.ans}}$。 该样例满足测试点 $6, 7$ 的约束条件。 **【样例 #6】** 见选手目录下的 $\textbf{\textit{icedrop/icedrop6.in}}$ 与 $\textbf{\textit{icedrop/icedrop6.ans}}$。 该样例满足测试点 $10\sim 13$ 的约束条件。 **【样例 #7】** 见选手目录下的 $\textbf{\textit{icedrop/icedrop7.in}}$ 与 $\textbf{\textit{icedrop/icedrop7.ans}}$。 该样例满足测试点 $14\sim 16$ 的约束条件。 **【样例 #8】** 见选手目录下的 $\textbf{\textit{icedrop/icedrop8.in}}$ 与 $\textbf{\textit{icedrop/icedrop8.ans}}$。 该样例满足测试点 $17, 18$ 的约束条件。 **【样例 #9】** 见选手目录下的 $\textbf{\textit{icedrop/icedrop9.in}}$ 与 $\textbf{\textit{icedrop/icedrop9.ans}}$。 该样例满足测试点 $21, 22$ 的约束条件。 **【样例 #10】** 见选手目录下的 $\textbf{\textit{icedrop/icedrop10.in}}$ 与 $\textbf{\textit{icedrop/icedrop10.ans}}$。 该样例满足测试点 $23 \sim 25$ 的约束条件。 **【数据范围】** 本题共 $25$ 个测试点，每个 $4$ 分。 对于所有测试数据，保证： - $1 \le n, q, a_i \le 5 \times 10^5$； - $1 \le l \le r \le n$。 ::cute-table{tuack} | 测试点编号 | $n \le$ | $q \le$ | $a_i \le$ | 特殊性质 | | :-: | :-: | :-: | :-: | :-: | | $1, 2$ | $500$ | $1$ | $500$ | AB | | $3, 4$ | $5000$ | ^ | $5 \times 10^5$ | ABC | | $5$ | ^ | ^ | ^ | AB | | $6, 7$ | $5 \times 10^5$ | ^ | ^ | ABC | | $8, 9$ | ^ | ^ | ^ | AB | | $10 \sim 13$ | ^ | ^ | ^ | AC | | $14 \sim 16$ | ^ | ^ | ^ | A | | $17, 18$ | ^ | $5 \times 10^5$ | ^ | BC | | $19, 20$ | ^ | ^ | ^ | B | | $21, 22$ | ^ | ^ | ^ | C | | $23 \sim 25$ | ^ | ^ | ^ | 无 | 特殊性质 A：对于所有询问都保证 $l = 1$，$r = n$。 特殊性质 B：对于所有 $1 \le i \le n$ 均有 $a_i > 1$。 特殊性质 C：对于所有 $1 \le i \le n$ 均存在 $k \in \N$ 使得 $a_i = 2^k$。