芸如是一位天才科学家，为中国阵营效力。她有着出众的才智，在几年的军旅生活中，芸如研制了许多高科技武器，使得中国军队的武备可以与厄普西隆阵营狡猾的研究成果相抗衡，甚至还可以和整个盟军部队分庭抗礼。
芸如很小的时候就已经开始展现自己的才华，并作为最优秀的幼儿被送往保密培训学校。在她入校的第一天，校长决定亲自考一考这位被外界奉为"天才"的小姑娘。
校长的问题是这样的：
在一个长度为N的数字序列A，有Q组询问，每组询问给定$l$和$r$：$ l \le r$，请求出$A[l]+A[l+1]+...+A[r]$的值。
由于这个结果可能很大，最终的结果要对10007取模（即取余数）。
多组数据输入，数据组数不超过10。
第一行是一个数字N，Q，表示序列A中元素的个数和询问组数。（$0 < N， Q \le 1e6$）
第二行是N个整数，第i个整数A[i]表示序列A中的第i个元素，保证均为非负整数，且在INT范围内。
接下来Q行，每行是两个用空格分隔的整数l和r（保证l和r不会超出序列A下标的范围，且$ l \le r$）。
注意序列A的下标从1开始。
对于每组数据，每个询问输出一行，为和值。
3 1
1 2 3
1 2
3
对20%的数据，$N, Q \le 100$
数据量较大，读入请勿用过慢读入方式。 该类提示以后上机将不再出现，请大家多总结相关经验