题目描述
小 A 最近在研究一个简单的问题:有 n 个数,其中第 i 个数为 ai,现在有 m 段区间,其中第 i 段区间左端点为 li,右端点为 ri。现在要求这 m 段区间上的数之和。也就是说要求:
i=1∑mj=li∑riaj
现在他想让你帮他计算这个问题。结果对 109+7 取模。
输入
第一行两个正整数 n 和 m。
第二行 n 个整数,其中第 i 个整数表示 ai。
接下来 m 行,每行两个正整数 li 和 ri。
输出
一个整数,表示求得的和。
样例
5 3
1 4 2 3 3
1 3
2 3
1 5
26
数据规模
- n≤106
- m≤106
- ∣ai∣≤109,其中 i∈[1,n]
- 1≤li≤ri≤n,其中 i∈[1,n]