时空限制

1.5S/512M

题目描述

对于 $S$ 的任意一个子集 $S_i \subseteq S$，定义 $f(S_i)$ 为： $S_i$ 中所有满足“在 $S_i$ 中出现次数为奇数”的元素之和。

例如：$S_i = \{2, 2, 3, 5, 5, 5\}$，其中 $2$ 出现了 $2$ 次，$3$ 出现了 $1$ 次，$5$ 出现了 $3$ 次。则 $f(S_i) = 3 + 5 = 8$。

给定一个长度为 $n$ 的数组 $a$。对于数组的任意一个子区间构成的可重集合 $S$，我们定义函数 $G(S)$ 为 $S$ 所有子集 $S_i$ 的 $f(S_i)$ 的平方之和对 $10^9+7$ 取模的结果：

$$G(S) = \big( \sum_{S_i \subseteq S} (f(S_i))^2 \big) \bmod{10^9+7} $$

现在有 $m$ 次询问，每次给定一个区间 $[l, r]$，请你求出该区间构成的可重集合 $S$ 的 $G(S)$ 值。

格式

输入格式

第一行包含两个整数 $n, m$，分别表示数组长度和询问次数。

第二行包含 $n$ 个整数，表示数组 $a$ 的元素。

接下来 $m$ 行，每行包含两个整数 $l, r$，表示询问的区间。

输出格式

对于每个询问，输出一个整数表示 $G(S) \bmod{10^9+7}$。

样例

样例输入 #1

3 2
2 2 3
1 2
1 3

样例输出 #1

8
76

样例解释 #1

• 对于询问 $[1, 2]$，$S = \{2, 2\}$。子集有 $\emptyset, \{a_1\}, \{a_2\}, \{a_1, a_2\}$。 $f$ 值分别为 $0, 2, 2, 0$。平方和 $G(S) = 0^2+2^2+2^2+0^2 = 8$。

数据规模

对于 $30\%$ 的数据，$1 \leq n \leq 10$，$1 \leq m \leq 10$。

对于 $100\%$ 的数据，$1 \le n, m \le 5 \times 10^5$，$1 \le a_i \le 10^9$，$1 \le l \le r \le n$。