背景

Ice Drop - Aqu3ra / 鏡音レン / MORE MORE JUMP！

このセカイを回す　唯一の魔法

让这世界回转的　唯一的魔法

题目描述

定义一个正整数序列是好的，当且仅当对任意正整数 $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$ 取模后的值。

10 6
1 1 2 1 1 6 1 3 5 1
1 5
4 5
8 10
2 8
1 10
6 9

42
3
8
187
475
17

10 1
2 3 5 6 12 4 7 8 9 10
1 10

27

10 1
64 1 1 1 1 96 1 1 1 262144
1 10

2371586

提示

【样例解释 #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$。