L. 宝石分组 / Gem

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

题目描述

收藏家小蓝有 n 个宝石， 其中第i 个宝石的亮度为 ai， 现在小蓝想把这些宝石分为 若干个组，满足每个宝石 恰好被分在一个组中。 对于一组宝石，若该组内有 k 个宝石，其亮度分别为 b1, b2, ..., bk，则小蓝认为这组 宝石的美观值为 (∑k i=1 bi)2 k2 。对于一组宝石的分组方案，小蓝认为其美观度为所有组的 美观值之和。 现在小蓝有 q 个问题，每个问题形如若要求在分组时每组宝石中的宝石的个数在 [l, r] 之间，则对于所有符合要求的分组方案，其美观度可以达到的 最大值是多少。 由于答案可能是一个很大的分数 a b ，为了方便输出，您只需要回答它对 10^9 + 7 取 模的结果， 即您需要求出一个在[0, 10^9 + 7) 之间的整数 c 使得 a ≡ bc( mod 10^9 + 7)， 可 以证明在本题的限制条件下，总存在符合条件的 c，且符合条件的 c 唯一。 特别地， 如果不存在符合要求的分组方案， 请输出 -1。

输入格式

从标准输入读入数据。 第一行输入两个正整数 n, q(1 ≤ n, q ≤ 5 × 10^5)，表示宝石总个数与问题个数。 第二行输入 n 个非负整数， 其中第i 个非负整数表示第 i 个宝石的亮度 ai(0 ≤ ai ≤ 10^8)。 接下来 q 行， 每行两个正整数l, r(1 ≤ l ≤ r ≤ 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}，此时美观值取到最大 值 625 ，对 10^9 + 7 取模的结果为 444444517。 对于第三个问题，最优的分组方案为 {13, 10}, {9, 7}, {5, 6}，此时美观值取到最大 值 453 ，对 10^9 + 7 取模的结果为 500000230。 对于第四个问题，要求每个组的大小必须为 4，而宝石总数 6 不是 4 的倍数，故在 分组时总会存在一些剩余的宝石无法分组，因此不存在符合条件的分组方案，所以输出 -1。