给定一个包含 $n$ 个两两不同的值的数组 $A = [a_0, a_1, \dots, a_{n-1}]$。我们将 $A$ 从 $l$ 开始到 $r$ 结束的排序子数组定义为对 $[a_l, a_{l+1}, \dots, a_r]$ 进行排序后得到的数组。例如，如果我们有数组 $[0, 2, 14, 6, 8, 10]$，则从 1 开始到 4 结束的排序子数组就是对 $[2, 14, 6, 8]$ 进行排序后得到的数组，即 $[2, 6, 8, 14]$。

给定 $q$ 个查询，每个查询包含两个整数 $l$ 和 $r$。对于每个查询，请输出 $A$ 从 $l$ 开始到 $r$ 结束的排序子数组中偶数位置上的元素之和。在此，我们假设所有数组均从 0 开始索引。

例如，考虑数组 $[0, 2, 14, 6, 8, 10]$ 和查询 $(1, 4)$。从 1 开始到 4 结束的子数组即为 $[2, 14, 6, 8]$。因此，从 1 开始到 4 结束的排序子数组为 $[2, 6, 8, 14]$。现在我们需要对偶数位置上的值求和，即 $2 + 8 = 10$。

请将答案对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 5 \cdot 10^4$; $1 \le q \le 2 \cdot 10^5$)：数组元素的数量和查询的数量。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i \le 10^9$; $a_i$ 两两不同)：数组的元素。

最后，接下来的 $q$ 行中，每行包含两个整数 $l$ 和 $r$ ($0 \le l \le r < n$)：我们所考虑的排序子数组的起始点和结束点。

输出格式

对于每个查询，输出一行，包含从 $l$ 开始到 $r$ 结束的排序子数组中偶数位置上的元素之和，对 $10^9 + 7$ 取模。

样例

输入 1

5 5
2 4 10 16 6
0 2
1 3
0 3
2 3
0 4

输出 1

12
20
12
10
24

输入 2

8 8
38 20 76 96 74 18 66 92
0 5
3 6
1 2
2 7
0 6
2 2
1 6
5 5

输出 2

132
92
20
184
226
76
160
18