题目描述

给定数组a,请你编写程序计算，T个区间(l,r)中 $\sum^{r}_{i=l}\sum^{r}_{j=i+1}(a[i]+a[j])$ 的值对10007取模的结果。

输入格式

第一行两个正整数n和T，分别表示数组a的元素个数和测试次数。 第二行n个整数，表示数组a的每一个元素(元素的值在1到100之间)。 接下来T行每行两个整数$l$和$r$，表示一个区间，保证$l<r$

输出格式

T行，每行1个正整数，表示结果

样例 #1

样例输入 #1

5 3
1 2 3 4 5
2 4
4 5
1 5

样例输出 #1

18 
9 
60

样例 #2

样例输入 #2

6 4
1 2 3 4 5 6
1 6
2 5
1 3
2 4

样例输出 #2

105 
42 
12 
18

提示

$1≤n,T≤100000$