时间限制： 1.0 秒 空间限制： 512 MiB

题目描述

收藏家小蓝有 \(n\) 个宝石，其中第 \(i\) 个宝石的亮度为 \(a_i\)，现在小蓝想把这些宝石分为若干个组，满足每个宝石恰好被分在一个组中。

对于一组宝石，若该组内有 \(k\) 个宝石，其亮度分别为 \(b_1, b_2, \ldots, b_k\)，则小蓝认为这组宝石的美观值为 \(\dfrac{\left(\sum_{i=1}^{k} b_i\right)^2}{k^2}\)。对于一组宝石的分组方案，小蓝认为其美观度为所有组的美观值之和。

现在小蓝有 \(q\) 个问题，每个问题形如：若要求在分组时每组宝石中的宝石个数在 \([l, r]\) 之间，则对于所有符合要求的分组方案，其美观度可以达到的最大值是多少。

由于答案可能是一个很大的分数 \(\dfrac{a}{b}\)，为了方便输出，您只需要回答它对 \(10^9 + 7\) 取模的结果，即您需要求出一个在 \([0, 10^9 + 7)\) 之间的整数 \(c\) 使得 \(a \equiv bc \pmod{10^9 + 7}\)，可以证明在本题的限制条件下，总存在符合条件的 \(c\)，且符合条件的 \(c\) 唯一。特别地，如果不存在符合要求的分组方案，请输出 -1。

输入格式

从标准输入读入数据。

第一行输入两个正整数 \(n, q\)（\(1 \le n, q \le 5 \times 10^5\)），表示宝石总个数与问题个数。

第二行输入 \(n\) 个非负整数，其中第 \(i\) 个非负整数表示第 \(i\) 个宝石的亮度 \(a_i\)（\(0 \le a_i \le 10^8\)）。

接下来 \(q\) 行，每行两个正整数 \(l, r\)（\(1 \le l \le r \le n\)），表示若要求在分组时每组宝石的个数在 \([l, r]\) 之间，对于所有符合要求的分组方案，其美观度可以达到的最大值。

输出格式

输出到标准输出。

输出共 \(q\) 行，其中第 \(i\) 行包含一个整数，表示第 \(i\) 个问题的答案，即当要求每组宝石的个数在第 \(i\) 个问题给出的区间之内时，所有符合要求的分组方案的美观度可以达到的最大值对 \(10^9 + 7\) 取模的结果。特别地，如果不存在符合要求的分组方案，请输出 -1。

样例

样例 1 输入

6 4
13 9 7 5 6 10
1 5
4 6
2 3
4 4

样例 1 输出

460
444444517
500000230
-1

样例 1 解释

对于第一个问题，最优的分组方案为每个宝石各分配到一个单独的组中，即 \(\{13\}, \{9\}, \{7\}, \{5\}, \{6\}, \{10\}\)，此时美观值为 \(460\)，取到最大值。

对于第二个问题，仅存在唯一的分组方案 \(\{13, 9, 7, 5, 6, 10\}\)，此时美观值取到最大值 \(\dfrac{625}{36}\)，对 \(10^9 + 7\) 取模的结果为 \(444444517\)。

对于第三个问题，最优的分组方案为 \(\{13, 10\}, \{9, 7\}, \{5, 6\}\)，此时美观值取到最大值 \(\dfrac{453}{4}\)，对 \(10^9 + 7\) 取模的结果为 \(500000230\)。

对于第四个问题，要求每个组的大小必须为 \(4\)，而宝石总数 \(6\) 不是 \(4\) 的倍数，故在分组时总会存在一些剩余的宝石无法分组，因此不存在符合条件的分组方案，所以输出 -1。