U281049 幻世「The World」

给定一个长为 $n$ 的数组 $a$，有 $q$ 次询问，每次给定一个区间 $[l,r]$，请求出 $$\prod_{l\le i,j\le r}\gcd(a_i,a_j)$$ 答案对 $10^9+7$ 取模。

第一行两个整数 $n,q$。 \ 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。\ 接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

对于每一次查询，输出一行一个整数代表答案。

### 样例解释 第一个样例，第一组询问的答案为 $\gcd(a_1,a_1)\times\gcd(a_1,a_2)\times\gcd(a_1,a_3)\times\gcd(a_2,a_1)\times\gcd(a_2,a_2)\times\gcd(a_2,a_3)\times\gcd(a_3,a_1)\times\gcd(a_3,a_2)\times\gcd(a_3,a_3)=1^8\times4=4$。 ### 数据范围 **本题采用捆绑测试。** 令 $v=\max_{i=1}^n a_i$。 | $\text{Subtask}$ | $n\le$ | $q\le$ | $v\le$ | 特殊性质 | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^3$ | $10^3$ | $10^3$ | 无 | $20$ | $2$ | $2\times 10^5$ | $1$ | $2\times 10^5$ | $l=1,r=n$ | $20$ | | $3$ | $2\times10^5$ | $2\times10^5$ | $10$ | 无 | $30$ | | $4$ | $5\times10^4$ |$5\times10^4$ |$5\times10^4$ | 无 | $40$ | | $5$ | $2\times10^5$ | $2\times10^5$ | $2\times10^5$ | 无 | $90$ | 对于 $100\%$ 的数据，保证 $1\le n,q,v\le 2\times 10^5$，$1\le l\le r\le n$。 ### 提示 本题的输入量约 4MB，输出量约 2MB，请自行选择合适的输入输出方式。 光速幂，用于求底数 $a$ 固定的幂。实现时选一个阈值 $b$，预处理 $a^0,a^1,\cdots,a^{b-1}$ 和 $a^b,a^{2b},\cdots,a^{k\times b}$，在求 $a^p$ 时直接求出 $a^{p\bmod b}\times a^{\lfloor\frac{p}{b}\rfloor\times b}$ 即可。